Springe direkt zu Inhalt

Monday Lectures

George Mertzios (Durham University, UK): Algorithmic Problems on Temporal Graphs

A temporal graph is a graph whose edge set changes over a sequence of discrete time steps. This can be viewed as a discrete sequence G_1, G_2, ... of static graphs, each with a fixed vertex set V. Research in this area is motivated by the fact that many modern systems are highly dynamic and relations (edges) between objects (vertices) vary with time. Although static graphs have been extensively studied for decades from an algorithmic point of view, we are still far from having a concrete set of structural and algorithmic principles for temporal graphs. Many notions and algorithms from the static case can be naturally transferred in a meaningful way to their temporal counterpart, while in other cases new approaches are needed to define the appropriate temporal notions. In particular, some problems become radically different, and often substantially more difficult, when the time dimension is additionally taken into account. In this talk we will discuss some natural but only recently introduced temporal problems and some algorithmic approaches to them.

Location: Online via Zoom.

Jan 31, 2022 | 02:15 PM

Klaus Heeger (Technische Universität Berlin): Stable Matchings Beyond Stable Marriage

Stable matchings are well-studied from computer science, mathematics, and economics. In the most basic setting, called Stable Marriage, there are two sets of agents. Each agent from one set has preferences over the agents from the other set. A matching assigns the agents into groups of two agents. A matching is called stable if there are no two agents preferring each other to the partners assigned to them. In this talk, we will review important parts of my forthcoming PhD thesis concerning the computational complexity of two extensions of this basic model: First, we assume that an instance of Stable Marriage is given, and the aim is to modify the instance (using as few "modifications" as possible) such that a given edge is part of some stable matching. Second, we assume that agents have preferences over sets of d-1 other agents (for some d>2). In this case, a matching matches agents into groups of size d, and a matching is stable if there are no d agents preferring to be matched together to being unmatched. While since 1991 this problem is known to be NP-complete, we study the case that the preferences of all agents are "similar".

Location: Online via Zoom.

Jan 31, 2022 | 04:00 PM s.t.

Neil Olver (London School of Economics and Political Science):

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor) / Online via Zoom.

Feb 07, 2022 | 02:15 PM

Carlos Amendola (Technische Universität München):

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor) / Online via Zoom.

Feb 14, 2022 | 02:15 PM

Marie Brandenburg (Max Planck Institut Leipzig):

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor) / Online via Zoom.

Feb 14, 2022 | 04:00 PM s.t.

Günter Rote (Freie Universität Berlin): The maximum number of minimal dominating sets in a tree

A tree with n vertices has at most 95 n/13 minimal dominating sets. The growth constant λ= 13 √95≈1.4194908 is best possible. It is obtained in a semi-automatic way as a kind of " dominant eigenvalue " of a bilinear operation on sextuples that is derived from the dynamic-programming recursion for computing the number of minimal dominating sets of a tree. The core of the method tries to enclose a set of sextuples in a six-dimensional geometric body with certain properties, which depend on some putative value of λ. This technique is generalizable to other counting problems, and it raises interesting questions about the "growth" of a general bilinear operation. We also derive an output-sensitive algorithm for listing all minimal dominating sets with linear set-up time and linear delay between successive solutions.

Location: Online via Zoom

Jan 24, 2022 | 02:15 PM

Ji Hoon Chun (Technische Universität Berlin): The Sausage Catastrophe in dimension 4

The Sausage Catastrophe (Jörg Wills) is the observation that in d = 3 and d = 4, the densest packing of n spheres is a sausage for small n and jumps to a full-dimensional packing for large n without passing through any intermediate dimensions. We denote the smallest value of n for which the densest packing is full-dimensional by k_d. We discuss some upper and lower bounds for k_3 and k_4, including k_3 ≤ 56 by Wills (1985) and k_4 < 375,769 by Gandini and Zucco (1992). We present some initial improvements to the upper bound for k_4 via extending the work of Gandini and Zucco.

Location: Online via Zoom

Jan 17, 2022 | 04:00 PM s.t.

María A. Hernández Cifre (Universitdad de Murcia): On discrete Brunn-Minkowski type inequalities

The classical Brunn-Minkowski inequality in the n-dimensional Euclidean space asserts that the volume (Lebesgue measure) to the power 1/n is a concave functional when dealing with convex bodies (non-empty compact convex sets). This result has become not only a cornerstone of the Brunn-Minkowski theory, but also a powerful tool in other related fields of mathematics. In this talk we will make a brief walk on this inequality, as well as on its extensions to the Lp-setting, for non-negative values of p. Then, we will move to the discrete world, either considering the integer lattice endowed with the cardinality, or working with the lattice point enumerator, which provides with the number of integer points contained in a given convex body: we will discuss and show certain discrete analogues of the above mentioned Brunn-Minkowski type inequalities in both cases. This is about joint works with Eduardo Lucas and Jesús Yepes Nicolás.

Location: Online via Zoom

Jan 17, 2022 | 02:15 PM

Vera Traub (ETH Zürich): Better-Than-2 Approximations for Weighted Tree Augmentation

The Weighted Tree Augmentation Problem (WTAP) is one of the most basic connectivity augmentation problems. It asks how to increase the edge-connectivity of a given graph from 1 to 2 in the cheapest possible way by adding some additional edges from a given set. There are many standard techniques that lead to a 2-approximation for WTAP, but despite much progress on special cases, the factor 2 remained unbeaten for several decades. In this talk we present two algorithms for WTAP that improve on the longstanding approximation ratio of 2. The first algorithm is a relative greedy algorithm, which starts with a simple, though weak, solution and iteratively replaces parts of this starting solution by stronger components. This algorithm achieves an approximation ratio of (1 + ln 2 + ε) < 1.7. Second, we present a local search algorithm that achieves an approximation ratio of 1.5 + ε (for any constant ε > 0). This is joint work with Rico Zenklusen.

Location: online via zoom

Jan 10, 2022 | 02:15 PM

Markus Schmid (Humboldt-Universität zu Berlin): Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number

We investigate the locality number, a recently introduced structural parameter for strings (with applications in pattern matching with variables), and its connection to two important graph-parameters, cutwidth and pathwidth. These connections allow us to show that computing the locality number is NP-hard, but fixed-parameter tractable, if parameterised by the locality number or by the alphabet size, which has been formulated as open problems in the literature. Moreover, the locality number can be approximated with ratio O(\sqrt{log(opt)} log(n))$. An important aspect of our work --- that is relevant in its own right and of independent interest --- is that we identify connections between the string parameter of the locality number on the one hand, and the famous graph parameters of cutwidth and pathwidth, on the other hand. These two parameters have been jointly investigated in the literature (with respect to exact, parameterised and approximation algorithms), and are arguably among the most central graph parameters that are based on "linearisations" of graphs. Most importantly, we relate cutwidth with pathwidth via the locality number, which results in an approximation preserving reduction that improves the currently best known approximation algorithm for cutwidth. [This is based on joint work with Katrin Casel, Joel D. Day, Pamela Fleischmann, Tomasz Kociumaka, and Florin Manea, published in Proc. ICALP'19.]

Location: Online via Zoom.

Dec 13, 2021 | 04:00 PM s.t.

Florin Manea (Universität Göttingen): Combinatorial String Solving

We consider a series of natural problems related to the processing of textual data, rooted in areas as diverse as information extraction, bioinformatics, algorithmic learning theory, or formal verification, and see how they can all be formalized within the same framework. In this framework, we say that a pattern $\alpha$ (that is, a string of string-variables and letters from a fixed alphabet $\Sigma$) matches another pattern $\beta$ if a text $T$, over $\Sigma$, can be obtained both from $\alpha$ and $\beta$ by uniformly replacing the variables of the two patterns by words over $\Sigma$. In the case when $\beta$ contains no variables, i.e., $\beta=T$ is a text, a match occurs if $\beta$ can be obtained from $\alpha$ by uniformly replacing the variables of $\alpha$ by words over $\Sigma$. The respective matching problems, i. e., deciding whether two given patterns match or a pattern and a text match, are computationally hard, but efficient algorithms exist for classes of patterns with restricted structure. In this talk, we overview a series of recent results in this area.

Location: Online via Zoom.

Dec 13, 2021 | 02:15 PM

Malte Renken (Technische Universität Berlin): Connectivity Thresholds in Random Temporal Graphs

We consider a simple model of a random temporal graph, obtained by assigning to every edge of an Erdős–Rényi random graph G_n,p a uniformly random presence time in the real interval [0, 1]. We study several connectivity properties of this random temporal graph model and uncover a surprisingly regular sequence of sharp thresholds at which these different levels of connectivity are reached. Finally, we discuss how our results can be transferred to other random temporal graph models. Based on joint work with Arnaud Casteigts, Michael Raskin, and Viktor Zamaraev.

Location: Online via Zoom

Dec 06, 2021 | 04:00 PM s.t.

Arnaud Casteigts (Université de Bordeaux): Spanners and connectivity problems in temporal graphs

A graph whose edges only appear at certain points in time is called a temporal graph. Such a graph is temporally connected if each ordered pair of vertices is connected by a path which traverses edges in chronological order (i.e., a temporal path). In this talk, I will focus on the concept of a temporal spanner, which is a subgraph of the input temporal graph that preserves temporal connectivity using as few edges (or labels) as possible. In stark contrast with standard graphs, it turns out that linear size spanners, and in fact, even sparse spanners (i.e., spanners with o(n ^2 ) edges) do not always exist in temporal graphs. After presenting basic notions and reviewing these astonishing negative results, I will present some good news as well; namely, sparse spanners always exist in *some* natural classes of temporal graphs. These include the cases when the underlying graph is complete (this talk) or when the labels are chosen at random (subsequent talk). If time permit, I will present two open questions, and discuss some recent attempts at solving them.

Location: Online via Zoom

Dec 06, 2021 | 02:15 PM

Benjamin Berendsohn (Freie Universität Berlin): Search trees on graphs

Search trees on graphs (STGs) are a generalization of binary search trees (BSTs). Where the key space of a BST is a totally ordered set, the key space of a STG is a graph. STGs are a relatively recent notion, but have been studied previously under different names, including elimination trees, maximal tubings, and vertex rankings. We survey some results. On the computational side, we consider a model of computation for STGs analagous to the BST model, and study which known results for BSTs can be adapted. On the combinatorial side, we study the diameter of certain polytopes called graph associahedra, which can be defined via STGs.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Nov 29, 2021 | 04:00 PM s.t.

Henry Adams (Institute of Science and Technology Austria): Open questions on clique complexes of graphs

The clique complex of a graph is a simplicial complex with a simplex for each clique. Clique complexes are frequently being computed in applications of topology to data, but we do not understand their algorithmic theory or their mathematical theory. I will introduce clique complexes of graphs, explain why applied topologists care about them, and survey open problems about the topology of clique complexes of unit disk graphs, powers of lattice graphs, and powers of hypercube graphs.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Nov 29, 2021 | 02:15 PM

Jonathan Leake (Technische Universität Berlin): Lorentzian polynomials on cones and the Heron-Rota-Welsh conjecture

About 5 years ago, the Heron-Rota-Welsh conjecture (log-concavity of the coefficients of the characteristic polynomial of a matroid) was proven by Adiprasito, Huh, and Katz via the exciting development of a new combinatorial Hodge theory for matroids. In very recent work with Petter Brändén, we have given a new short "polynomial proof" of the Heron-Rota-Welsh conjecture. Our proof uses an extension of the theory of Lorentzian polynomials to convex cones. In this talk, I will briefly discuss the basics of Lorentzian (aka completely log-concave) polynomials, and then I will give an overview of our new proof of the Heron-Rota-Welsh conjecture.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Nov 22, 2021 | 04:00 PM s.t.

Markus Brill (Technische Universität Berlin): Approval-Based Apportionment

In the apportionment problem, a fixed number of seats must be distributed among parties in proportion to the number of voters supporting each party. We study a generalization of this setting, in which voters cast approval ballots over parties, such that each voter can support multiple parties. This approval-based apportionment setting generalizes traditional apportionment and is a natural restriction of approval-based multiwinner elections, where approval ballots range over individual candidates. Using techniques from both apportionment and multiwinner elections, we identify rules that generalize the D'Hondt apportionment method and that satisfy strong axioms which are generalizations of properties commonly studied in the apportionment literature. In fact, the rules we discuss provide representation guarantees that are currently out of reach in the general setting of multiwinner elections: First, we demonstrate that extended justified representation is compatible with committee monotonicity (also known as house monotonicity). Second, we show that core-stable committees are guaranteed to exist and can be found in polynomial time. Joint work with Paul Gölz, Dominik Peters, Ulrike Schmidt-Kraepelin, and Kai Wilker.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Nov 22, 2021 | 02:15 PM

Stefan Kuhlmann (Technische Universität Berlin): Lattice width of lattice-free polyhedra and height of Hilbert bases

A polyhedron defined by an integral valued constraint matrix and an integral valued right-hand side is lattice-free if it does not contain an element of the integer lattice. In this talk, we present a link between the lattice-freeness of polyhedra, the diameter of finite abelian groups and the height of Hilbert bases. As a result, we will be able to prove novel upper bounds on the lattice width of lattice-free pyramids if a conjecture regarding the height of Hilbert bases holds. Further, we improve existing lattice width bounds of lattice-free simplices. All our bounds are independent of the dimension and solely depend on the maximal minors of the constraint matrix. The second part of the talk is devoted to a study of the above-mentioned conjecture. We completely characterize the Hilbert basis of a pointed polyhedral cone when all the maximal minors of the constraint matrix are bounded by two in absolute value. This can be interpreted as an extension of a well-known result which states that the Hilbert basis elements lie on the extreme rays if the constraint matrix is unimodular, i.e., all maximal minors are bounded by one in absolute value. This is joint work with Martin Henk and Robert Weismantel.

Location: online via Zoom

Nov 15, 2021 | 04:00 PM s.t.

Tim Netzer (Uni Innsbruck): Free Semialgebraic Geometry and Quantum Information Theory

Quantum information theory studies how quantum information can be represented, stored, processed and sent. On the mathematical side this often involves the study of tensor products and decompositions of positive matrices, as well as positive maps. These are also natural objects in free semialgebraic geometry, where positivity of non-commutative objects are studied from a geometric viewpoint. In this talk I will give an introduction to some important concepts in both areas, and demonstrate how results and methods from either field can be successfully employed in the other. This is joint ongoing work between the group of Gemma De las Cuevas and my own research group in Innsbruck.

Location: online via Zoom

Nov 15, 2021 | 02:15 PM

Davide Lofano (Technische Universität Berlin): Hadamard Matrix Torsion

After a brief overview about torsion in homology and examples of complexes with small torsion and few vertices we will  focus our attention on a particular series of examples. In particular, we will construct a series HMT(n) of 2-dimensional simplicial complexes with huge torsion, |H_1(HMT(n))|=|det(H(n))|=n^(n/2), where the construction is based on the Hadamard matrices H(n) and they have linearly many vertices in n. Our explicit series improves a previous construction by Speyer, narrowing the gap to the highest possible asymptotic torsion growth achieved by Newman via a randomized construction.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Nov 08, 2021 | 04:00 PM s.t.

Manfred Scheucher (Technische Universität Berlin): Erdős-Szekeres-type Problems on Planar Point Sets

In 1935, Erdős and Szekeres proved that, for every positive integer k, every sufficiently large point set contains a "k-gon", that is, a subset of k points which is the vertex set of a convex polygon. Their theorem is a classical result in both, combinatorial geometry and Ramsey theory, and motivated a lot of further research including numerous modifications and extensions of the theorem. In this talk we discuss some results and methods that played an essential role in the study of k-gons and the variant of "k-holes".

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Nov 08, 2021 | 02:15 PM

Letícia Mattos (Freie Universität Berlin): Singularity of random symmetric matrices

Let M_n be a uniformly-chosen random symmetric n x n matrix with entries in {-1,1}. What is the probability for det(M_n)=0? A wellknown conjecture states that the probability of this event is asymptotically equal to the probability that two of the rows or columns of M_n are equal (up to a factor of +-1) and hence is equal to \Theta(n^2 2^{-n}). We developed an inverse Littlewood-Offord theorem in Z^n_p that applies under very mild conditions and made progress towards this conjecture, showing that the probability is bounded by exp(-c\sqrt{n}). Joint work with Marcelo Campos, Robert Morris and Natasha Morrison.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Nov 01, 2021 | 04:00 PM s.t.

Florian Frick (Carnegie Mellon University and FU Berlin): Topological methods in graph theory

When we study the structure of a graph, we encounter parameters that are local (such as the clique number) and parameters that are global (such as the chromatic number). Topology provides tools to measure global phenomena. I will explain the hidden topology of the global structure of graphs for problems such as chromatic numbers, covering and matching problems, and partitions into independent sets with various constraints.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Nov 01, 2021 | 02:15 PM

Simona Boyadzhiyska (Freie Universität Berlin): Ramsey simplicity of random graphs

We say that a graph G is q-Ramsey for another graph H if any q-coloring of the edges of G yields a monochromatic copy of H. Much of the research related to Ramsey graphs is concerned with determining the smallest possible number of vertices in a q-Ramsey graph for a given H, known as the q-color Ramsey number of H . In the 1970s, Burr, Erdős, and Lovász initiated the study of another graph parameter in the context of Ramsey graphs: the minimum degree.  A straightforward argument shows that, if G is a minimal q-Ramsey graph for H, then we must have δ(G) >= q(δ(H) - 1) + 1, and we say that H is q-Ramsey simple if this bound can be attained. In this talk, we will ask how typical Ramsey simplicity is; more precisely, we will discuss for which pairs p and q the random graph G(n,p) is almost surely q-Ramsey simple. This is joint work with Dennis Clemens, Shagnik Das, and Pranshu Gupta.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Oct 25, 2021 | 04:00 PM s.t.

Penny Haxell (University of Waterloo): Tashkinov trees - This talk is also introduction to upcoming mini course "Edge colouring of multigraphs" Oct. 26-29

The technique of Tashkinov trees is an important tool that has been used to obtain many significant results on edge colouring of multigraphs. We describe the method and its main motivation, the famous Goldberg-Seymour conjecture from the 1970's. We also outline several results from the last decade that have used the Tashkinov trees technique. This talk is intended as an introduction , overview and survey to accompany the upcoming short course "Edge colouring of multigraphs and the Tashkinov trees method" (Oct 26-29) .

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Oct 25, 2021 | 02:15 PM

Raphael Steiner (Technische Universität Berlin): The dichromatic number-a survey

The dichromatic number of a digraph is the smallest number of acyclic subsets of vertices (not spanning a directed cycle) that can be used to cover its vertex-set. This parameter is a natural extension of the chromatic number to directed graphs and has been introduced in 1980 by Erdös and Neumann-Lara. Since 2000, many groups of authors have studied this parameter intensively and in various settings. In this talk, I will give a small survey of this topic, which has concerned me quite a bit in the last 3-epsilon years. I will also mention own results obtained during my PhD at appropriate places.

Location: online

Jul 12, 2021 | 04:00 PM s.t.

Frédéric Havet (INRIA Sophia-Antipolis): Unavoidability and universality of digraphs

A digraph F is n-unadoidable} (resp. n-universal) if it is contained in every tournament of order n (resp. n-chromatic digraph). Well-known theorems imply that there is an n F such that F is n F -unavoidable (resp. n F -universal) if and only if F is acyclic, (resp. an oriented forest). However, determining the smallest n F for which it occurs is a challenging question. In this talk, we survey the results on unavoidability and universality and detail some recent recults obtained with various co-authors.

Location: online

Jul 12, 2021 | 02:15 PM

Ansgar Freyer (Technische Universität Berlin): Shaking a convex body in order to count its lattice points

We prove inequalities on the number of lattice points inside a convex body K in terms of its volume and its successive minima. The successive minima of a convex body have been introduced by Minkowski and since then, they play a major role in the geometry of numbers. A key step in the proof is a technique from convex geometry known as Blascke's shaking procedure by which the problem can be reduced to anti-blocking bodies, i.e., convex bodies that are "located in the corner of the positive orthant". As a corollary of our result, we will obtain an upper bound on the number of lattice points in K in terms of the successive minima, which is equivalent to Minkowski's Second Theorem, giving a partial answer to a conjecture by Betke et al. from 1993. This is a joint work with Eduardo Lucas Marín.

Location: online

Jul 05, 2021 | 04:00 PM s.t.

Papa Sissokho (Illinois State University): Geometry of the minimal Solutions of a linear diophantine Equation

Let a 1 ,...,a n and b 1 ,...,b m be fixed positive integers, and let S denote the set of all nonnegative integer solutions of the equation x 1 a 1 +...+x n a n =y 1 b 1 +...+y m b m . A solution (x 1 ,...,x n ,y 1 ,...,y m ) in S is called minimal if it cannot be expressed as the sum of two nonzero solutions in S.  For each pair (i,j), with 1 ≤ i ≤ n and 1 ≤ j ≤ m, the solution whose only nonzero coordinates are x i = b j and y j = a i is called a generator .  We show that every minimal solution is a convex combination of the generators and the zero-solution. This proves a conjecture of Henk-Weismantel and, independently, Hosten-Sturmfels.

Location: online

Jul 05, 2021 | 02:15 PM

Gorav Jindal (Technische Universität Berlin): Arithmetic Circuit Complexity of Division and Truncation

Given n-variate polynomials f,g,h such that f=g/h, where both g and h are computable by arithmetic circuits of size s, we show that f can be computed by a circuit of size poly(s, deg(h)). This solves a special case of division elimination for high-degree circuits (Kaltofen’87 & WACT’16). This result is an exponential improvement over Strassen’s classic result (Strassen’73) when deg(h) is poly(s) and deg(f) is exp(s), since the latter gives an upper bound of poly(s, deg(f)). The second part of this work deals with the complexity of computing the truncations of uni-variate polynomials or power series. We first show that the truncations of rational functions are easy to compute.  We also prove that the truncations of even very simple algebraic functions are hard to compute,unless integer factoring is easy. This is a joint work with Pranjal Dutta, Anurag Pandey and Amit Sinhababu. A pre-print can be found at https://eccc.weizmann.ac.il/report/2021/072/  .

Location: online

Jun 28, 2021 | 04:00 PM s.t.

Xavier Allamigeon (Inria and Ecole Polytechnique): Formalizing the theory of polyhedra in a proof assistant

In this talk, I will present the project Coq-Polyhedra that aims at formalizing the theory of polyhedra as well as polyhedral computations in the proof assistant Coq. I will explain how the intuitionistic nature of the logic of a proof assistant like Coq requires to define basic properties of polyhedra in a quite different way than is usually done, by relying on a formal proof of the simplex method. I will also focus on the formalization of the faces of polyhedra, and present a mechanism which automatically introduces an appropriate representation of a polyhedron or a face, depending on the context of the proof. I will demonstrate the usability of this approach by establishing some of the most important combinatorial properties of faces, namely that they constitute a family of graded atomistic and coatomistic lattices closed under interval sublattices, as well as Balinski’s theorem on the d-connectedness of the graph of d-polytopes. Finally, I will discuss recent progress on the formal computation of the graph of a polytope directly within the proof assistant, thanks to a certified algorithm that checks a posteriori the output of Avis’ vertex enumeration library lrslib. Joint work with Quentin Canu, Ricardo D. Katz and Pierre-Yves Strub.

Location: online

Jun 28, 2021 | 02:15 PM

Patrick Morris (Freie Universität Berlin): Triangle factors in pseudorandom graphs

An (n, d, λ)-graph is an n vertex, d-regular graph with second eigenvalue in absolute value λ. When λ is small compared to d, such graphs have pseudo-random properties. A fundamental question in the study of pseudorandom graphs is to find conditions on the parameters that guarantee the existence of a certain subgraph. A celebrated construction due to Alon gives a triangle-free (n, d, λ)-graph with d = Θ(n^2/3) and λ = Θ(d^2/n). This construction is optimal as having λ = o(d^2/n) guarantees the existence of a triangle in a (n, d, λ)-graph. Krivelevich, Sudakov and Szab ́o (2004) conjectured that if n ∈ 3N and λ = o(d^2/n) then an (n, d, λ)-graph G in fact contains a triangle factor: vertex disjoint triangles covering the whole vertex set.  In this talk, we discuss a solution to the conjecture of Krivelevich, Sudakov and Szab ́o. The result can be seen as a clear distinction between pseudorandom graphs and random graphs, showing that essentially the same pseudorandom condition that ensures a triangle in a graph actually guarantees a triangle factor. In fact, even more is true: as a corollary to this result and a result of Han, Kohayakawa, Person and the author, we can conclude that the same condition actually guarantees that such a graph G contains every graph on n vertices with maximum degree at most 2.

Location: online

Jun 21, 2021 | 04:00 PM s.t.

Alexey Pokrovskiy (University College London): Linear size Ramsey numbers of hypergraphs

The size-Ramsey number of a hypergraph H is the minimum number of edges in a hypergraph G whose every 2-edge-colouring contains a monochromatic copy of H. This talk will be about showing that the size-Ramsey number of r-uniform tight path on n vertices is linear in n. Similar results about hypergraph trees and their powers will also be discussed. This is joint work with Letzter and Yepremyan.

Location: online

Jun 21, 2021 | 02:15 PM

Alex Postnikov (MIT): Polypositroids

Polypositroids is a class of convex polytopes defined to be those polytopes that are simultaneously generalized permutohedra (or polymatroids) and alcoved polytopes. Whereas positroids are the matroids arising from the totally nonnegative Grassmannian,polypositroids are "positive" polymatroids. We parametrize polypositroids using Coxeter necklaces and balanced graphs, and describe the cone of polypositroids by extremal rays and facet inequalities. We generalize polypositroids to an arbitrary finite Weyl group W, and connect them to cluster algebras and to generalized associahedra. We also discuss membranes, which are certain triangulated surfaces. They extend the notion of plabic graphs from positroids to polypositroids. The talk is based on a joint work with Thomas Lam.

Location: online

Jun 14, 2021 | 04:30 PM

Davide Lofano (Technische Universität Berlin): Random Simple-Homotopy Theory

A standard task in topology is to simplify a given finite presentation of a topological space. Bistellar flips allow to search for vertex-minimal triangulations of surfaces or higher-dimensional manifolds, and elementary collapses are often used to reduce a simplicial complex in size and potentially in dimension. Simple-homotopy theory, as introduced by Whitehead in 1939, generalizes both concepts. We take on a random approach to simple-homotopy theory and present a heuristic algorithm to combinatorially deform non-collapsible, but contractible complexes (such as triangulations of the dunce hat, Bing's house or non-collapsible balls that contain short knots) to a point. The procedure also allows to find substructures in complexes, e.g., surfaces in higher-dimensional manifolds or subcomplexes with torsion in lens spaces. (Joint work with Bruno Benedetti, Crystal Lai, and Frank Lutz.)

Location: online

Jun 14, 2021 | 02:45 PM

Michael Joswig (Technische Universität Berlin): Tropical bisectors and Voronoi diagrams

We consider norms in real vector spaces where the unit ball is an arbitrary convex polytope, possibly centrally symmetric.  In contrast with the Euclidean norm, the topological shape of bisectors may be complicated.  Our first main result is a formula for the Betti numbers of bisectors of three points in sufficiently general position. Specializing our results to the tropical polyhedral norm then yields structural results and algorithms for tropical Voronoi diagrams.  The tropical distance function plays a key role in current applications of tropical geometry. Joint work with Francisco Criado and Francisco Santos.

Location: online

Jun 07, 2021 | 02:15 PM

Aniket Shah (Ohio State University): A q-analogue of Brion's identity

Rogers-Szego polynomials are a family of orthogonal polynomials on the circle. We introduce a generalization of these polynomials which depend on the data of a polytope and prove a vertex sum formula for them when the polytope is smooth. This formula recovers Brion's formula when the parameter q is set to 0.

Location: online

May 17, 2021 | 04:00 PM s.t.

Max Klimm (Technische Universität Berlin): Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games

We settle the complexity of computing an equilibrium in atomic splittable congestion games with player-specific affine cost functions as we show that the computation is PPAD-complete. To prove that the problem is contained in PPAD, we develop a homotopy method that traces an equilibrium for varying flow demands of the players. A key technique for this method is to describe the evolution of the equilibrium locally by a novel block Laplacian matrix where each entry of the Laplacian is a Laplacian again. These insights give rise to a path following formulation eventually putting the problem into PPAD. For the PPAD—hardness, we reduce from computing an approximate equilibrium for bimatrix win-lose games. As a byproduct of our analyse, we obtain that also computing a multi-class Wardrop equilibrium with class-dependent affine cost functions is PPAD-complete as well. As another byproduct, we obtain an algorithm that computes a continuum of equilibria parametrised by the players’ flow demand. For games with player-independent costs, this yields an output-polynomial algorithm. (Joint work with Philipp Warode)

Location: online

May 10, 2021 | 02:15 PM

Chris Eur (Stanford University): Tautological classes of matroids

We introduce certain torus-equivariant classes on permutohedral varieties which we call "tautological classes of matroids" as a new geometric framework for studying matroids. Using this framework, we unify and extend many recent developments in matroid theory arising from its interaction with algebraic geometry. We achieve this by establishing a Chow-theoretic description and a log-concavity property for a 4-variable transformation of the Tutte polynomial, and by establishing an exceptional Hirzebruch-Riemann-Roch-type formula for permutohedral varieties that translates between K-theory and Chow theory.  This is a joint work with Andrew Berget, Hunter Spink, and Dennis Tseng.

Location: online

May 03, 2021 | 04:30 PM

Matthieu Rosenfeld (LIRMM): Bounding the number of sets defined by a given MSO formula on trees

Monadic second order logic can be used to express many classical notions of sets of vertices of a graph as for instance: dominating sets, induced matchings, perfect codes, independent sets, or irredundant sets. Bounds on the number of sets of any such family of sets are interesting from a combinatorial point of view and have algorithmic applications. Many such bounds on different families of sets over different classes of graphs are already provided in the literature. In particular, Rote recently showed that the number of minimal dominating sets in trees of order n is at most 95^(n/13) and that this bound is asymptotically sharp up to a multiplicative constant. We build on his work to show that what he did for minimal dominating sets can be done for any family of sets definable by a monadic second-order formula. I will first illustrate the general technique with a really simple concrete example ( Dominating independent sets). Then I will explain how to generalize this into a more general technique. I will end my talk by mentioning a few of the results obtained with this technique.

Location: online

Apr 26, 2021 | 04:00 PM s.t.

Kolja Knauer (Universitat de Barcelona): On sensitivity in Cayley graphs

Recently, Huang proved the Sensitivity Conjecture, by showing that every set of more than half the vertices of the $d$-dimensional hypercube $Q_d$ induces a subgraph of maximum degree at least $\sqrt{d}$. This is tight by a result of Chung, F\"uredi, Graham, and Seymour. Huang asked whether similar results can be obtained for other highly symmetric graphs. In this lecture we study Huang's question on Cayley graphs of groups. We show that high symmetry alone does not guarantee similar behavior and present three infinite families of Cayley graphs of unbounded degree that contain induced subgraphs of maximum degree $1$ on more than half the vertices. In particular, this refutes a conjecture of Potechin and Tsang, for which first counterexamples were shown recently by Lehner and Verret. The first family consists of dihedrants. The second family are star graphs, these are edge-transitive Cayley graphs of the symmetric group. All members of the third family are $d$-regular containing an induced matching on a $\frac{d}{2d-1}$-fraction of the vertices. This is largest possible and answers a question of Lehner and Verret. On the positive side, we consider Cayley graphs of Coxeter groups, where a lower bound similar to Huang's can be shown. A generalization of the construction of Chung, F\"uredi, Graham, and Seymour shows that this bound is tight for products of Coxeter groups of type $\mathbf{A_n}$, $\mathbf{I_n}(2k+1)$, most exceptional cases and not far from optimal in general. Then, we show that also induced subgraphs on more than half the vertices of Levi graphs of projective planes and of the Ramanujan graphs of Lubotzky, Phillips, and Sarnak have unbounded degree. This yields more classes of Cayley graphs with properties similar to the ones provided by Huang's results. However, in contrast to Coxeter groups these graphs have no large subcubes. Joint with Ignacio Garcia-Marco.

Location: online

Apr 26, 2021 | 02:15 PM

Peter Bürgisser (Technische Universität Berlin): Optimization, Complexity and Invariant Theory

Invariant and representation theory studies symmetries by means of group actions and is a well established source of unifying principles in mathematics and physics. Recent research suggests its relevance for complexity and optimization through quantitative and algorithmic questions. The goal of the lecture is to give an introduction to new algorithmic and analysis techniques that extend convex optimization from the classical Euclidean setting to a general geodesic setting. We also point out surprising connections to a diverse set of problems in different areas of mathematics, statistics, computer science, and physics. The lecture is mainly based on this joint article with Cole Franks, Ankit Garg, Rafael Oliveira, Michael Walter and Avi Wigderson: http://arxiv.org/abs/1910.12375

Location: online

Feb 22, 2021 | 02:15 PM

Helena Bergold (Fern Universität Hagen): Topological Drawings meet Classical Theorems of Convex Geometry

In this talk we discuss classical theorems from Convex Geometry such as Carathéodory's Theorem in a more general context of topological drawings of complete graphs. In a (simple) topological drawing the edges of the graph are drawn as simple closed curves such that every pair of edges has at most one common point. Triangles of topological drawings can be viewed as convex sets. This gives a link to convex geometry. Our main result is a generalization of Kirchberger's Theorem that is of purely combinatorial nature. For this we introduce a structure called ''generalized signotopes'' which are a combinatorial generalization of topological drawings. We discuss further properties of generalized signotopes. Joint work with Stefan Felsner, Manfred Scheucher, Felix Schröder and Raphael Steiner.

Location: online

Feb 08, 2021 | 02:15 PM

Michaela Borzechowski: One-Permutation-Discrete-Contraction is UEOPL-hard

The complexity class Unique End of Potential Line (UEOPL) was introduced in 2018 by Fearnley et al. and contains many interesting search problems. UEOPL captures problems that have either by definition a unique solution, like the Arrival problem, or that are promised to have a unique solution by some property, like the P-Matrix linear complementary problem. Furthermore the problems in UEOPL have the property that the candidate solutions can be interpreted as an exponentially large graph which form a line, i.e. each node has in and out degree at most 1. The solution of each problem is at the end of that line. In 2017, Daskalakis, Tzamos and Zampetakis proved the problem of finding a fixpoint of a contraction map in a continuous space whose existence is guaranteed by the Banach fixed point theorem to be CLS-complete. A discrete version of the contraction problem, called One-Permutation-Discrete-Contraction, is proven to be the first UEOPL-complete problem. This proof is particularly interesting because it is currently the only one of its kind and lays the groundwork for future UEOPL-completeness proofs. This talk will provide an overview of the reduction from the problem Unique-End-of-Potential-Line to One-Permutation-Discrete-Contraction as well as correcting some errors that were done in the original paper.

Location: online

Jan 25, 2021 | 02:15 PM

Pavle Blagojević (Freie Universität Berlin): Ten years in one lecture

Ten years ago, in February 2011, I joined the group of Günter M. Ziegler at Freie Universität Berlin. Now, ten years later, I will show you some of the problems in Geometric and Topological Combinatorics that intrigued us, some of which we managed to solve, and sketch some of the crucial ideas, methods, and the tools we had to develop in order to answer them.  We will see how  -- work on the Bárány-Larman conjecture on colored point sets in the plane   gave birth to the Optimal colored Tverberg theorem,  -- the constraint method collected all classical Tverberg type results under one roof    and opened a door towards counter-examples to the topological Tverberg conjecture. Furthermore, we will illustrate how the search for convex partitions of a polygon into pieces of equal area and equal perimeter forced us to  -- study the topology of the classical configuration spaces,  -- construct equivariant cellular models for them,  -- prove a new version of an equivariant Goresky-MacPherson formula for complements of arrangements,  -- revisit a classical vanishing theorem of Frederick Cohen, and explain why these answers are related to the existence of highly regular embeddings and periodic billiard trajectories. Finally, we will talk about  -- equi-partitions of convex bodies by affine hyperplanes, and  -- greedy convex partitions of many measures. These results are joint work with, in chronological order, Günter M. Ziegler, Benjamin Matschke, Florian Frick, Albert Haase, Nevena Palić, Günter Rote, and Johanna K. Steinmeyer.

Location: online

Jan 18, 2021 | 04:00 PM s.t.

Florian Frick (Carnegie Mellon University): New applications of the Borsuk--Ulam theorem

The classical Borsuk--Ulam theorem states that any continuous map from the d-sphere to d-space identifies two antipodal points. Over the last 90 years numerous applications of this result across mathematics have been found. I will survey some recent progress, such as results about the structure of zeros of trigonometric polynomials, which are related to convexity properties of circle actions on Euclidean space, a proof of a 1971 conjecture that any closed spatial curve inscribes a parallelogram, and finding well-behaved smooth functions to the unit circle in any closed finite codimension subspace of square-intergrable complex functions.

Location: online

Jan 18, 2021 | 02:15 PM

Maria Dostert (Royal Institute of Technology): Exact semidefinite programming bounds for packing problems

In the first part of the talk, I present how semidefinite programming methods can provide upper bounds for various geometric packing problems, such as kissing numbers, spherical codes, or packings of spheres into a larger sphere. When these bounds are sharp, they give additional information on optimal configurations, that may lead to prove the uniqueness of such packings. For example, we show that the lattice E 8  is the unique solution for the kissing number problem on the hemisphere in dimension 8. However, semidefinite programming solvers provide approximate solutions, and some additional work is required to turn them into an exact solution, giving a certificate that the bound is sharp. In the second part of the talk, I explain how, via our rounding procedure, we can obtain an exact rational solution of a semidefinite program from an approximate solution in floating point given by the solver. This is a joined work with David de Laat and Philippe Moustrou.

Location: online

Jan 11, 2021 | 04:00 PM s.t.

CANCELED: Raman Sanyal (Goethe-Universität Frankfurt): From counting lattice points to counting free segments and back

This talk has been canceled on short notice, and will take place at a later time. Ehrhart theory, the art of counting lattice points in convex polytopes, is a cornerstone of the interplay of combinatorics and geometry. Many important combinatorial objects can be modelled as lattice points in polytopes and counting lattice points with respect to dilation yields deep results in combinatorics. Conversely, the combinatorics of polytopes provides a powerful framework for the computation of these counting functions with numerous algebraic/combinatorial consequnces and challenges. A lattice polytope is free if does not contain lattice points other than its vertices. Klain (1999) suggested a generalization of Ehrhart theory by counting free polytopes with $k$ vertices contained in dilates of a given polytope. For $k=1$, this is precisely Ehrhart theory. Determining these counting functions for $k > 1$ is quite challenging. For $k=2$ (free segments), this is related to counting lattice points visible from each other. In the talk I will discuss joint work with Sebastian Manecke on counting free segments in dilates of unimodular simplices. Our main tool is a number-theoretic variant of Ehrhart theory which can be computed using classical results from geometry. The talk will be scenic tour (with impressions from the unusual summer 2020).

Location: online

Jan 11, 2021 | 02:15 PM

Alp Müyesser: Rainbow factors and trees

Generalizing a conjecture of Aharoni, Joos and Kim asked the following intriguing question. Let H be a graph on m edges, and let G_i (1<=i<=m) be a sequence of m graphs on the common vertex set [n]. What is the weakest minimum degree restriction we can impose on each G_i to guarantee a rainbow copy of H? Joos and Kim answered this question when H is a Hamilton cycle or a perfect matching. We provide an asymptotic answer when H is an F-factor, or a spanning tree with maximum degree o(n/log n). This is joint work with Richard Montgomery and Yani Pehova.

Location: online

Jan 04, 2021 | 03:00 PM s.t.

Sampada Kolhatkar: Bivariate chromatic polynomials of mixed graphs

For a graph G=(V,E), the chromatic polynomial X_G counts the number of vertex colourings as a function of number of colours. Stanley’s reciprocity theorem connects the chromatic polynomial with the enumeration of acyclic orientations of G. One way to prove the reciprocity result is via the decomposition of chromatic polynomials as the sum of order polynomials over all acyclic orientations. From the Discrete Geometry perspective, the decomposition is as the sum of Ehrhart polynomials through real braid arrangement. Beck, Bogart, and Pham proved the analogue of this reciprocity theorem for the strong chromatic polynomials for mixed graph. Dohmen–Pönitz–Tittmann provided a new two variable generalization of the chromatic polynomial for undirected graphs. We extend this bivariate chromatic polynomial to mixed graphs, provide a deletion-contraction like formula and study the colouring function geometrically via hyperplane arrangements.

Location: online

Jan 04, 2021 | 02:00 PM s.t.

Jannik Peters: Efficiency and Stability in Euclidean Network Design

We study the recently proposed Euclidean Generalized Network Creation Game by Bilò et al.[SPAA 2019] and investigate the creation of (beta,gamma)-networks, which are in beta-approximate Nash equilibrium and have a total cost of at most gamma times the optimal cost. In our model we have n agents corresponding to points in Euclidean space create costly edges among themselves to optimize their centrality in the created network. Our main result is a simple O(n^2)-time algorithm that computes a (beta,beta)-network with low beta for any given set of points. Along the way, we significantly improve several results from Bilò et al. and we asymptotically resolve a conjecture about the Price of Anarchy.

Location: online

Dec 14, 2020 | 04:00 PM s.t.

Dante Luber: Boundary Complexes for Moduli Spaces of Curves

In 2016, Noah Giansiracua showed that a collection of boundary divisors in the moduli space of genus-0 n-pointed curves has nonempty intersection if and only if all pairwise intersections are nonempty. This result is equivalent to showing that the boundary complex associated to such a moduli space is a flag complex. Kyla Quillin extended Giansiracusa's result to most moduli spaces of genus-g n-pointed curves. We give a complete classification of all (g,n) pairs for which the boundary complex is a flag complex.

Location: online

Dec 14, 2020 | 03:00 PM s.t.

Matthias Himmelmann: Generalized Principal Component Analysis for Algebraic Varieties

The Buchberger-Möller algorithm is a famous symbolic method for finding all polynomials that vanish on a point cloud. It has even been extended to noisy samples. However, the resulting variety does not necessarily represent the topological or geometric structure of the data well. By making use of the Vandermonde matrix, it is possible to find polynomials of a prescribed degree vanishing on the samples. As this matrix is severely ill-conditioned, modifications are necessary. By making use of statistical and algebro-geometric techniques, an algorithm for learning a vanishing ideal that represents the data points‘ geometric properties well is presented. It is investigated that this method -- among various other desirable properties -- is more robust against perturbations in the data than the original algorithm.

Location: online

Dec 14, 2020 | 02:00 PM s.t.

Kemal Rose:

Location: online

Dec 07, 2020 | 03:00 PM s.t.

Stefan Mengel (CNRS): A Biased Introduction to Decomposable Negation Normal Forms

Decomposable Negation Normal Forms (DNNF) are a class of Boolean circuits first introduced by Darwiche in 2001 in the context of artificial intelligence. Since then they have found applications as a flexible framework for encoding Boolean functions in other areas of computer science like theoretical computer science and database theory. In this talk, I will introduce DNNF, discuss some uses and sketch how one can show bounds on their size.

Location: online

Nov 30, 2020 | 02:15 PM

Lisa Sauermann (IAS, Princeton): On the extension complexity of low-dimensional polytopes

It is sometimes possible to represent a complicated polytope as a projection of a much simpler polytope. To quantify this phenomenon, the extension complexity of a polytope P is defined to be the minimum number of facets in a (possibly higher-dimensional) polytope from which P can be obtained as a (linear) projection. In this talk, we discuss some results on the extension complexity of random d-dimensional polytopes (obtained as convex hulls of random points on either on the unit sphere or in the unit ball), and on the extension complexity of polygons with all vertices on a common circle. Joint work with Matthew Kwan and Yufei Zhao.

Location: online

Nov 16, 2020 | 02:15 PM

Markus Bläser (Universität Saarbrücken): Irreversibility of tensors of minimal border rank and barriers for fast matrix multiplication

Determining the asymptotic algebraic complexity of matrix multiplication is a central problem in algebraic complexity theory. The best upper bounds on the so-called exponent of matrix multiplication if obtained by starting with an "efficient" tensor, taking a high power and degenerating a matrix multiplication out of it. In the recent years, several so-called barrier results have been established. A barrier result shows a lower bound on the best upper bound for the exponent of matrix multiplication that can be obtained by a certain restriction starting with a certain tensor. We prove the following barrier over the complex numbers: Starting with a tensor of minimal border rank satisfying a certain genericity condition, except for the diagonal tensor, it is impossible to prove ω = 2 using arbitrary restrictions. This is astonishing since the tensors of minimal border rank look like the most natural candidates for designing fast matrix multiplication algorithms. We prove this by showing that all of these tensors are irreversible, using a structural characterisation of these tensors. Joint work with Vladimir Lysikov.

Location: online

Nov 02, 2020 | 02:15 PM

Sophie Spirkl (University of Waterloo): k-coloring graphs with forbidden induced subgraphs

A k-coloring of a graph G is a function c that assigns an integer between 1 and k to every vertex of G such that c(u) is not equal to c(v) for every edge uv of G. Deciding, given a graph G, whether G has a k-coloring, is NP-hard for all k at least 3. In this talk, we will consider what happens when we restrict the input, that is: For a graph H and integer k, what is the complexity of deciding if a given graph G with no induced subgraph isomorphic to H has a k-coloring? We know the answer for many pairs H and k. Possibly the most interesting open cases are those in which H is a path; I will talk about recent results and open questions related to this.

Location: online

Oct 26, 2020 | 02:15 PM

Tillmann Miltzow (Utrecht University): A practical algorithm with performance guarantees for the art-gallery problem

Given a closed simple polygon P, we say two points p,q see each other if the segment pq is fully contained in P. The art gallery problem seeks a minimum size set G⊂P of guards that sees P completely. The only known algorithm to solve the art gallery problem exactly is attributed to Sharir and uses algebraic methods. As the art gallery problem is ∃R-complete, it seems impossible to avoid algebraic methods without additional assumptions. To circumvent this problem, we introduce the notion of vision stability. In order to describe vision stability, consider an enhanced guard that can see "around the corner" by an angle of δ or a diminished guard whose vision is "blocked" by an angle δ by reflex vertices. A polygon P has vision stability δ if the optimal number of enhanced guards to guard P is the same as the optimal number of diminished guards to guard P. We will argue that most relevant polygons are vision-stable. We describe a one-shot algorithm that computes an optimal guard set for vision-stable polygons using polynomial time besides solving one integer program. We implemented an iterative version of the vision-stable algorithm. Its practical performance is slower, but comparable to other state-of-the-art algorithms. Our iterative algorithm is a variation of the one-shot algorithm. It delays some steps and only computes them only when deemed necessary. Given a chord c of a polygon, we denote by n(c) the number of vertices visible from c. The chord-width of a polygon is the maximum n(c) over all possible chords c. The set of vision-stable polygons admits an FPT algorithm when parametrized by the chord-width. Furthermore, the one-shot algorithm runs in FPT time when parameterized by the number of reflex vertices. Joint work by Simon Hengeveld & Tillmann Miltzow.

Location: online

Oct 19, 2020 | 04:00 PM s.t.

Mikkel Abrahamsen (University of Copenhagen): A framework for ∃R-completeness of two-dimensional packing problems

We show that many natural two-dimensional packing problems are algorithmically equivalent to finding real roots of multivariate polynomials. A two-dimensional packing problem is defined by the type of pieces, containers, and motions that are allowed. The aim is to decide if a given set of pieces can be placed inside a given container. The pieces must be placed so that they are pairwise interior-disjoint, and only motions of the allowed type can be used to move them there. We establish a framework which enables us to show that for many combinations of allowed pieces, containers, and motions, the resulting problem is ∃R-complete. This means that the problem is equivalent (under polynomial time reductions) to deciding whether a given system of polynomial equations and inequalities with integer coefficients has a real solution. We consider packing problems where only translations are allowed as the motions, and problems where arbitrary rigid motions are allowed, i.e., both translations and rotations. When rotations are allowed, we show that the following combinations of allowed pieces and containers are ∃R-complete: - simple polygons, each of which has at most 8 corners, into a square, - convex objects bounded by line segments and hyperbolic curves into a square, - convex polygons into a container bounded by line segments and hyperbolic curves. Restricted to translations, we show that the following combinations are ∃R-complete: - objects bounded by segments and hyperbolic curves into a square, - convex polygons into a container bounded by segments and hyperbolic curves. Joint work by Mikkel Abrahamsen, Tillmann Miltzow, and Nadja Seiferth. The paper has been accepted for FOCS.

Location: online

Oct 19, 2020 | 02:15 PM

Amitabh Basu (Johns Hopkins University Baltimore): Complexity of cutting plane and branch-and-bound algorithms - cancelled

We present some results on the theoretical complexity of branch-and-bound (BB) and cutting plane (CP) algorithms for mixed-integer optimization. In the first part of the talk, we study the relative efficiency of BB and CP, when both are based on the same family of disjunctions. We focus on variables disjunctions and split disjunctions. We extend a result of Dash to the nonlinear setting which shows that for convex 0/1 problems, CP does at least as well as BB, with variable disjunctions. We sharpen this by showing that there are instances of the stable set problem where CP does exponentially better than BB. We further show that if one moves away from 0/1 polytopes, this advantage of CP over BB disappears; there are examples where BB finishes in O(1) time, but CP takes infinitely long to prove optimality, and exponentially long to get to arbitrarily close to the optimal value (for variable disjunctions). Finally, we show that if the dimension is considered a fixed constant, then the situation reverses and BB does at least as well as CP (up to a polynomial blow up). In the second part of the talk, we will discuss the conjecture that the split closure has polynomial complexity in fixed dimension, which has remained open for a while now even in 2 dimensions. We settle it affirmatively in two dimensions, and complement it with a polynomial time pure cutting plane algorithm for 2 dimensional IPs based on split cuts.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Jul 13, 2020 | 02:15 PM

Mikkel Abrahamsen (University of Copenhagen): Geometric Multicut: Shortest Fences for Separating Groups of Objects in the Plane - cancelled

We study the following separation problem: Given a collection of colored objects in the plane, compute a shortest "fence" F, i.e., a union of curves of minimum total length, that separates every two objects of different colors. Two objects are separated if F contains a simple closed curve that has one object in the interior and the other in the exterior. We refer to the problem as GEOMETRIC k-CUT, where k is the number of different colors, as it can be seen as a geometric analogue to the well-studied multicut problem on graphs. We first give an O(n^4 log^3 n)-time algorithm that computes an optimal fence for the case where the input consists of polygons of two colors and n corners in total. We then show that the problem is NP-hard for the case of three colors. Finally, we give a 4/3*1.2965-approximation algorithm. Joint work with Panos Giannopoulos, Maarten Löffler, and Günter Rote. Presented at ICALP 2019.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Apr 27, 2020 | 02:15 PM

Alina Stancu (Concordia University Montréal): Examples and usage of discrete curvature in convex geometry problems - cancelled

Discretization of curvature has found numerous applications particularly in the modeling of moving smooth boundaries separating two different materials and image processing. Nonetheless, there are usually several ways to address discretization of curvature, even in the case of a 1-dimenional object (a curve) depending in essence of the role of the curvature in the physical process or the problem considered. I will present two models of discretization of curvature that I was personally involved with in relation to two geometric problems where the objects considered were also convex.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Apr 20, 2020 | 02:15 PM
Feb 10, 2020 | 05:00 PM s.t.

José Samper (Max Planck Institut Leipzig): Dual matroid polytopes and the independence complex of a matroid

A shelling order of a simplicial/polytopal complex is an ordering of the top dimensional faces that allows us to understand various properties of the underlying complex (when it exists). Empirically, some shelling orders are better than others in the sense that they are easier to analyze or come equipped with . This is especially notable for complexes that admit many shelling orders, like polytopes and and matroid independence complexes. We propose a strange connection, linking shelling orders of dual matroid polytopes to shelling orders of independence complexes. In particular, we show that several classical theorems about shellability of matroids have geometric interpretations. We use this to address to propose a new strategy for a 1977 conjecture of R. Stanley about face numbers of independence complexes: that the h-vector is a pure O-sequence. The talk is based on joint work with Alex Heaton.

Feb 10, 2020 | 04:00 PM s.t.

Lionel Pournin (Université Paris 13): Recent results on the diameter of lattice polytopes

Several new results about the largest possible diameter of a lattice polytope contained in the hypercube [0,k]^d, a quantity related to the complexity of the simplex algorithm, will be presented. Upper bounds on this quantity have been known for a couple of decades and have been improved recently. In this lecture, conjecturally sharp lower bounds on this quantity will be presented for all d and k, as well as exact asymptotic estimates when d is fixed and k grows large. These lower bounds are obtained by computing the largest diameter a lattice zonotope contained in the hypercube [0,k]^d can have, answering a question by Günter Rote. This talk is based on joint work with Antoine Deza and Noriyoshi Sukegawa.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Feb 10, 2020 | 02:15 PM

Yanitsa Pehova (University of Warwick): Characterisation of quasirandom permutations by a pattern sum

We say that a sequence {π _ i } of permutations is quasirandom if, for each k>1 and each σ∈ S _ k , the probability that a uniformly chosen k-set of entries of π _ i induces σ tends to 1/ k ! as i tends to infinity. It is known that a much weaker condition already forces π _ i to be quasirandom; namely, if the above property holds for all σ∈ S 4 . We further weaken this condition by exhibiting sets S⊆ S 4 , such that if randomly chosen four entries of π _ i induce an element of S with probability tending to | S |/24, then {π _ i } is quasirandom. Moreover, we are able to completely characterise the sets S with this property. In particular, there are exactly ten such sets, the smallest of which has cardinality eight. This is joint work with Timothy Chan, Daniel Král', Jon Noel, Maryam Sharifzadeh and Jan Volec.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Feb 03, 2020 | 04:00 PM s.t.

Sándor Kisfaludi-Bak (Max Planck Institut Saarbrücken): Separators and exact algorithms for geometric intersection graphs

Given n ball-like objects in some metric space, one can define a geometric intersection graph where the vertices correspond to objects, and edges are added for pairs of objects with a non-empty intersection. A separator of a graph is a small or otherwise "nice" vertex set whose removal disconnects the graph into two roughly equal parts. In this talk, we will see some separator theorems for intersection graphs in Euclidean and hyperbolic space. One can use these separators to design simple divide and conquer algorithms for several classical NP-hard problems. It turns out that well-designed separators often lead to subexponential algorithms with optimal running times (up to constant factors in the exponent) under the Exponential Time Hypothesis (ETH).

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Feb 03, 2020 | 02:15 PM

Michał Włodarczyk (Eindhoven): Losing treewidth by separating subsets: on approximation of vertex/edge deletion problems

Consider the problem of deleting the smallest set S of vertices (resp. edges) from a given graph G such that the induced subgraph (resp. subgraph) G \ S belongs to some class H . I will cover the case where graphs in H have treewidth bounded by t , and give a general framework to obtain approximation algorithms basing on two ingredients: 1) approximation algorithms for the k -Subset Separator problem, 2) FPT algorithms parameterized by the solution size. For the vertex deletion setting, this new framework combined with the current best result for k -Subset Vertex Separator, improves approximation ratios for basic problems such as k -Treewidth Vertex Deletion and Planar F Vertex Deletion. Our algorithms are simpler than previous works and give the first deterministic and uniform approximation algorithms under the natural parameterization. I will talk about what it means for several important graph classes and how the bounded treewidth property is exploited. I will present a sketch of the proof for the H Vertex Deletion algorithm and explain the differences between deleting vertices or edges.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Jan 27, 2020 | 05:00 PM s.t.

Gweneth Anne McKinley (MIT, Cambridge, USA): Super-logarithmic cliques in dense inhomogeneous random graphs

In the theory of dense graph limits, a graphon is a symmetric measurable function W from [0,1] ^2 to [0,1]. Each graphon gives rise naturally to a random graph distribution, denoted G ( n , W ), that can be viewed as a generalization of the Erdös-Rényi random graph. Recently, Dolezal, Hladky, and Mathe gave an asymptotic formula of order  log n   for the size of the largest clique in G ( n , W ) when W is bounded away from 0 and 1. We show that if W is allowed to approach 1 at a finite number of points, and displays a moderate rate of growth near these points, then the clique number of G ( n , W ) will be of order √ n almost surely. We also give a family of examples with clique number of order n ^ c for any c in (0,1), and some conditions under which the clique number of  G ( n , W ) will be o (√ n ) or ω(√ n ). This talk assumes no previous knowledge of graphons.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Jan 27, 2020 | 04:00 PM s.t.

Haim Kaplan (Tel Aviv University): Privately Learning Thresholds

We study the problem of computing a point in the convex hull, and the related problem of computing a separating hyperplane, under the constraint of differential privacy . Intuitively, differential privacy means that our output should be robust to small changes in the input (for example to adding or deleting a point). We study the minimum size of the input needed to achieve such a private computation (sample complexity) and its time complexity. Even in one dimension the problem is non-trivial and we will first focus on this case. Several interesting open problems will be presented as well. No previous background on differential privacy will be assumed.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Jan 27, 2020 | 02:15 PM

Gorav Jindal (Aalto University, Helsinki): On the Complexity of Symmetric Polynomials

The fundamental theorem of symmetric polynomials states that for a symmetric polynomial f _Sym in C [ x 1 , x 2 ,..., x n ], there exists a unique "witness" f in C [ y 1 , y 2 ,..., y n ] such that f _Sym= f ( e 1 , e 2 ,..., e n ), where the e_ i 's are the elementary symmetric polynomials. In this work, we study the arithmetic complexity L ( f ) of the witness f as a function of the arithmetic complexity L ( f _Sym) of f _Sym. We show that the arithmetic complexity L ( f ) of f is bounded by poly( L ( f _Sym),deg( f ), n ). Prior to this work, only exponential upper bounds were known for L ( f ). The main ingredient in our result is an algebraic analogue of Newton’s iteration on power series. As a corollary of this result, we show that if VP is not equal to VNP then there are symmetric polynomial families which have super-polynomial arithmetic complexity. This is joint work with Markus Bläser.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Jan 20, 2020 | 05:00 PM s.t.

Alan Arroyo (Institute of Science and Technology Austria): Obstructions in graph drawings

Many nice results in graph theory involve the characterization of a graph class in terms of a set of forbidden obstructions. In this talk I will consider the problem of understanding whether a class of graph drawings can be characterized by a set of forbidden obstructions.  I will do an overview on interesting recent results that fall under this theme, but I will emphasize more on those related to geometric arrangements.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Jan 20, 2020 | 04:00 PM s.t.

Holger Dell (IT University of Copenhagen): Counting and sampling small subgraphs

In this talk, we discuss various algorithmic techniques used for counting and sampling subgraphs in a large input graph. The focus of the talk is on the mathematical foundations. We start with the beautiful technique of Color-Coding (Alon, Yuster, Zwick 1995), and we discuss various generalizations based on group algebras (Koutis 2008) and on the exterior algebra (Brand, D, Husfeldt 2018). These techniques are most useful for sampling, which is equivalent to approximate counting. On the other hand, the fastest known algorithm to exactly count subgraphs that are isomorphic to a graph H  (Curticapean, D, Marx 2017) is based on the foundations of Lovász' theory of graph limits.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Jan 20, 2020 | 02:15 PM

Shahrzad Haddadan (MPI Saarbrücken): Algorithms for top-k Lists and Social Networks

Today’s massive and dynamic data sets have motivated many computer scientists and mathematicians to study classical problems in combinatorics and graph theory in various settings. In certain settings the algorithms’ access to the data is restricted while in others the resources are limited. In this talk we explore such settings in three directions: ranking of objects, property testing in social networks and finding communities in dynamic graphs. In the first part, we discuss algorithms on permutations as well as prefixes of permutations also known as top- k lists. The study of later particularly arises in big data scenarios when analysis of the entire permutation is costly or not interesting. We start by discussing random walks on the set of full rankings or permutations of n objects, a set whose size is n !. Since 1990s to today, various versions of this problem have been studied, each for different motivation. The second part of the talk is devoted to property testing in social networks: given a graph, an algorithm seeks to approximate several parameters of a graph just by accessing the graph by means of oracles and while querying these oracles as few times as possible. We introduce a new oracle access model which is applicable to social networks, and assess the complexity of estimating parameters such as number of users (vertices) in this model. In the third part of the talk, we introduce a new dynamic graph model which is based on triadic closure: a friendship is more likely to be formed between a pair of users with a larger number of mutual friends. We find upper bounds for the rate of graph evolution in this model and using such bounds we devise algorithms discovering communities. I will finish this talk by proposing new directions and presenting related open problems.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Jan 13, 2020 | 05:00 PM s.t.

Andrei Asinowski (Universität Klagenfurt): Vectorial kernel method and patterns in lattice paths

A directed lattice path is a polygonal line which starts at the origin and consists of several vectors of the form (1, y) (where y belongs to a fixed set of integers) appended to each other. Enumeration of different kinds of lattice paths (walks/bridges/meanders/excursions) was accomplished by Banderier and Flajolet in 2002. We refine and generalize their results by studying lattice paths that avoid a fixed pattern (or several patterns). To this end, we develop a "vectorial kernel method" – a unified framework for enumeration of words generated by a counter automaton. Another improtant tool is the "autocorrelation polynomial" that encodes self-overlappings of a pattern, and its generalization: the "mutual correlation matrix" for several patterns. (This talk is based on joint works with Cyril Banderier, Axel Bacher, Bernhard Gittenberger and Valerie Rointer.)

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Jan 13, 2020 | 04:00 PM s.t.

Eric Fusy (École Polytechnique Paris): Bijections between families of walks using oriented planar maps

When counting walks (with a given step-set), an equi-enumeration phenomenom is often observed between a stronger constraint on the domain and a stronger constraint on the position of the endpoint (a classical one-dimensional example is the fact that positive walks of length 2 n are in bijection with walks of length 2 n ending at 0, both being counted by the central binomial coefficient). I will show examples of such relations for 2 d walks where the equi-enumeration can be bijectively explained using planar maps endowed with certain orientations (Schnyder woods, bipolar orientations).

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Jan 13, 2020 | 02:15 PM

Lukas Kühne (Hebrew University of Jerusalem): Matroid representations by c-arrangements are undecidable

A matroid  is a combinatorial object based on an abstraction of linear independence in vector spaces and forests in graphs. It is a classical question to determine whether a given matroid is representable as a vector configuration over a field. Such a matroid is called linear. This talk is about a generalization of that question from vector configurations to c-arrangements. A c-arrangement for a fixed c is an arrangement of dimension c subspaces such that the dimensions of their sums are multiples of c. Matroids representable as c-arrangements are called multilinear matroids. We prove that it is algorithmically undecidable whether there exists a c such that a given matroid has a c-arrangement representation. In the proof, we introduce a non-commutative von Staudt construction to encode an instance of the uniform word problem for finite groups in matroids of rank three. The talk is based on joint work with Geva Yashfe.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Jan 06, 2020 | 04:00 PM s.t.

Frank Sottile (Texas University): Irrational toric varieties and the secondary polytope

The secondary fan of a point configuration A in R^n encodes all regular subdivisions of A. These subdivisions also record all limiting objects obtained by weight degenerations of the irrational toric variety X_A parameterized by A. The secondary fan is the normal fan of the secondary polytope. We explain a functorial construction of R^n-equivariant cell complexes from fans that, when applied to the secondary fan, realizes the secondary polytope as the moduli space of translations and degenerations of X_A. This extends the work of Kapranov, Sturmfels and Zelevinsky (who established this for complex toric varieties when A is integral) to all real configurations A.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Jan 06, 2020 | 02:15 PM

Alexander Heaton (Max Planck Institut Leipzig): Applications of algebra to the geometry of materials

The upcoming Thematic Einstein Semester entitled "Geometric and Topological Structure of Materials" will focus on recent advancements in computational materials science. In this talk, we will present two interesting areas where algebra can play a role in future research. First, in the design and analysis of novel materials, questions of rigidity of frameworks arise. For generic configurations, matroid-theoretic and combinatorial techniques can be used to study rigidity. But the frameworks arising in applications are rarely generic, therefore deciding local rigidity presents a difficult computational problem which connects to the numerical algebraic geometry of varieties and semi-algebraic sets. Second, both point configurations and also polycrystalline materials give rise to cellular decompositions of 3-dimensional space. We will discuss how a Fourier-type analysis of these cells can be used to understand their approximate symmetry. The representation theory of SO(3) and its finite subgroups can be used to extract Fourier coefficients from the surface normal density of a given cell.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Dec 16, 2019 | 04:00 PM s.t.

Paweł Dłotko (Swansea University): Topology in Action

In this talk we will focus on a number of practical problems, originating from the theory of dynamical systems and materials science, all the way to medicine and data science. In all of them we will identify certain shapes that carry important information required to solve those problems. We will introduce standard and new tools of Topological Data Analysis and see how to apply them to the discussed scenarios.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Dec 16, 2019 | 02:15 PM

Marcel Celaya (Georgia Institute of Technology): The linear span of lattice points in a half-open lattice parallelepiped

The problem of deciding if there exists a lattice point inside a half-open parallelepiped on a given rational hyperplane is known to be NP-complete. In contrast, the question of deciding if all lattice points in a half-open parallelepiped lie on a given hyperplane has a much nicer answer. In this talk I will explain this answer in detail, and outline some applications.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Dec 09, 2019 | 04:00 PM s.t.

Svante Linusson (Königlich Technische Hochschule Stockholm): Limit shape of shifted staircase SYT

A shifted tableau of staircase shape has row lengths n,n-1,...,2,1 adjusted on the right side and numbers increasing along rows and columns. Let the number in a box represent the height of a point above that box, then we have proved that the points for a uniformly chosen random shifted staircase SYT in the limit converge to a certain surface in three dimensions.  I will present this result and also how this implies, via properties of the Edelman–Greene bijection, results about random 132-avoiding sorting networks, including limit shapes for trajectories and intermediate permutations. (Based on joint work with Samu Potka and Robin Sulzgruber.)

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Dec 09, 2019 | 02:15 PM

Talks of the Einstein Workshop on Polytopes and Algebraic Geometry

  Monday Dec. 2 (ZIB) Tuesday Dec. 3 (ZIB) Wednesday Dec. 4 (Hotel Steglitz Int.) 08.30 - 09.00 Registration     09.00 - 10.00 Benjamin Braun Johannes Hofscheier Winfried Bruns   Coffee break 10.30 - 10.55 Andrés R. Vindas Meléndez Andrea Petracci Alessio D’Alì 11.00 - 11.25 Davide Bolognini María-Cruz Fernández-Fernández Eliana Duarte 11.30 - 11.55 Carlos Alejandro Alfaro Montufar Oguzhan Yürük Daniel Tamayo Jiménez   Lunch 14.00 - 15.00 Alex Fink Thomas Kahle Alexander Borisov 15.10 - 15.35 Filip Cano Córdoba Karin Schaller Marta Panizzut   Coffee break 16.10 - 17.10 Matthias Beck Matthias Schymura Fatemeh Mohammadi

Location: Freie Universität Berlin Zuse Institut Berlin Takustr. 7 14195 Berlin

Dec 02, 2019 | 02:00 PM s.t.

Manfred Scheucher (Techniche Universität Berlin): Topological Drawings meet SAT Solvers and Classical Theorems of Convex Geometry

In a simple topological drawing of the complete graph $K_n$, vertices are mapped to points in the plane, edges are mapped to simple curves connecting the corresponding end points, and each pair of edges intersects at most once, either in a common vertex or in a proper crossing. We discuss an axiomatization of simple drawings and for various sub-classes and present a SAT model. With the aid of modern SAT solvers, we investigate some famous and important classical theorems from Convex Geometry (such as Caratheodory’s, Helly's, Kirchberger's Theorem, and the Erdös-Szekeres Theorem) in the context of simple drawings. This is joint work with Helena Bergold, Stefan Felsner, Felix Schröder, and Raphael Steiner. Research is in progress.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Nov 25, 2019 | 04:00 PM s.t.

Georg Loho (London School of Economics and Political Science): Signed tropical convexity

Convexity for the max-plus algebra has been studied from different directions including discrete geometry, scheduling, computational complexity. As there is no inverse for the max-operation, this used to rely on an implicit non-negativity assumption. We remove this restriction by introducing `signed tropical convexity'. This allows to exhibit new phenomena at the interplay between computational complexity and geometry. We obtain several structural theorems including a new Farkas lemma and a Minkowski-Weyl theorem for polytopes over the signed tropical numbers. Our notion has several natural formulations in terms of balance relations, polytopes over Puiseux series and hyperoperations.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Nov 25, 2019 | 02:15 PM

Ansgar Freyer (Technische Universität Berlin): Discrete analogs of an inequality by Meyer

In 1988, Mathieu Meyer presented a lower bound on the volume of a convex body in terms of the volumes of its sections with the coordinate hyperplanes. Our aim is to "discretize" this inequality by replacing the volume by the lattice point enumerator. It turns out that such a discrete analog cannot exist for general convex bodies. Moreover, it will not imply its continuous counterpart. We prove inequalities for the case of o-symmetric bodies (using arithmetic progressions) and unconditional bodies (by proving a universal bound for the lattice point enumerator of unconditional lattice polytopes). Moreover, the talk will touch on a reverse inequality and other related problems.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Nov 18, 2019 | 04:00 PM s.t.

Matthias Reitzner (Universität Osnabrück): Stars of Empty Simplices

Consider an n-element point set in general position in d-dimensional space. For a k-element subset the degree is the number of empty d-simplices with this k-set as base. We investigate the maximal degree of a random point set consisting of n independently and uniformly chosen points from a compact set.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Nov 18, 2019 | 02:15 PM

Raphael Steiner (Technische Universität Berlin): Majority Colorings of Sparse Digraphs

A majority coloring of a directed graph is a vertex-coloring in which every vertex has the same color as at most half of its out-neighbors. Kreutzer, Oum, Seymour, van der Zypen and Wood proved that every digraph has a majority 4-coloring and conjectured that every digraph admits a majority 3-coloring. We verify this conjecture for digraphs with chromatic number at most 6 or dichromatic number at most 3. We obtain analogous results for list coloring: We show that every digraph with list chromatic number at most 6 or list dichromatic number at most 3 is majority 3-choosable. We deduce that digraphs with maximum out-degree at most 4 or maximum degree at most 7 are majority 3-choosable. On the way to these results we investigate digraphs admitting a majority 2-coloring. We show that every digraph without odd directed cycles is majority 2-choosable. We answer an open question posed by Kreutzer et al. negatively, by showing that deciding whether a given digraph is majority 2-colorable is NP-complete. Finally we deal with a fractional relaxation of majority coloring proposed by Kreutzer et al. and show that every digraph has a fractional majority 3.9602-coloring. We show that every digraph D with sufficiently large minimum out-degree has a fractional majority-(2+ε)-coloring. Joint work with Michael Anastos, Ander Lamaison and Tibor Szabó.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Nov 11, 2019 | 04:00 PM s.t.

Tibor Szabó (Freie Universität Berlin): Turán numbers, projective norm graphs, quasirandomness

The Turán number of a (hyper)graph H, defined as the maximum number of (hyper)edges in an H-free (hyper)graph on a given number of vertices, is a fundamental concept of extremal graph theory. The behaviour of the Turán number is well-understood for non-bipartite graphs, but for bipartite H there are more questions than answers. A particularly intriguing half-open case is the one of complete bipartite graphs. The projective norm graphs $NG(q,t)$ are algebraically defined graphs which provide tight constructions in the Tur\'an problem for complete bipartite graphs $H=K_{t,s}$ when $s > (t-1)!$. The $K_{t,s}$-freeness of $NG(q,t)$ is a very much atypical property: in a random graph with the same edge density a positive fraction of $t$-tuples are involved in a copy of $K_{t,s}$. Yet, projective norm graphs are random-like in various other senses. Most notably their second eigenvalue is of the order of the square root of the degree, which, through the Expander Mixing Lemma, implies further quasirandom properties concerning the density of small enough subgraphs. In this talk we explore how far this quasirandomness goes. The main contribution of our proof is the estimation, and sometimes determination, of the number of solutions of certain norm equation system over finite fields. Joint work with Tomas Bayer, Tam\'as M\'esz\'aros, and Lajos R\'onyai.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Nov 11, 2019 | 02:15 PM

Liana Yepremyan (University of Oxford): On the size Ramsey number of bounded powers of bounded degree trees

We say a graph G is Ramsey for a graph H if every red/blue edge-colouring of the edges of G contains a monochromatic copy of H. The size Ramsey number of a graph H is defined to be the minimum number of edges among all graphs which are Ramsey for H. The study of size Ramsey numbers originated by the work of Erdős, Faudree, Rousseau and Schelp from 1970's. This number was studied for graphs including paths, cycles, powers of paths and cycles, trees of bounded degree. For all mentioned graphs it was shown that the size Ramsey number grows linearly in the number of vertices ("is linear"). This line of research was inspired by a question of Beck who asked whether the size Ramsey number is linear for graphs of bounded degree. Later this was disproved by Rödl and Szemerédi. In this talk I will present our recent result showing that fixed powers of bounded degree trees also have linear size Ramsey number. Equivalently, this result says that all graphs of bounded degree and bounded treewidth have linear size Ramsey number. We also obtain off-diagonal version of this result. Many exciting problems remain open. This is joint work with Nina Kam\v{c}ev, Anita Liebenau and David Wood.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Nov 04, 2019 | 04:00 PM s.t.

Günter Rote (Freie Universität Berlin): Lattice paths with states, and counting geometric objects via production matrices

We consider paths in the plane governed by the following rules: (a) There is a finite set of states. (b) For each state q , there is a finite set S ( q ) of allowable "steps" (( i,j) , q ′). This means that from any point ( x , y ) in state q , we can move to ( x + i , y + j ) in state q ′. We want to count the number of paths that go from (0,0) in some starting state q 0 to the point ( n ,0) without ever going below the x -axis. There are strong indications that, under some natural technical conditions, the number of such paths is asymptotic to C ^ n /(√ n ^ 3 ), for some "growth constant" C which I will show how to compute. I will discuss how lattice paths with states can be used to model asymptotic counting problems for some non-crossing geometric structures (such as trees, matchings, triangulations) on certain structured point sets. These problems were recently formulated in terms of so-called production matrices. This is ongoing joint work with Andrei Asinowski and Alexander Pilz.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Nov 04, 2019 | 02:15 PM

Benjamin Hauskeller (Humboldt-Universität zu Berlin): Dynamic Query Evaluation with Sublinear Update Time

Dynamic Query Evaluation considers the problem of evaluating a database query on a database using the following framework: In a preprocessing phase the query and an initial database are used to build a data structure which can enumerate the query result on the current database. Upon updates to the database the data structure is adapted to the new database. Research is then interested in the time needed for the preprocessing, the handling of an update, and the maximal delay between tuples during enumeration. In this talk I will present a new class of queries that can be maintained with linear preprocessing time, sublinear update time and constant delay.

Location: Humboldt-Universität zu Berlin Institut für Informatik Humboldt-Kabinett (between House 3&4 / 1st Floor [British Reading]) Johann von Neumann-Haus Rudower Chaussee 25 12489 Berlin

Oct 28, 2019 | 04:00 PM s.t.

Alexandre Vigny (Universität Bremen): Query enumeration and nowhere dense classes of graphs

Given a query q and a relational structure D the enumeration of q over D consists in computing, one element at a time, the set q(D) of all solutions to q on D. The delay is the maximal time between two consecutive output and the preprocessing time is the time needed to produce the first solution. Idealy, we would like to have constant delay enumeration after linear preprocessing. Since this it is not always possible to achieve, we need to add restriction to the classes of structures and/or queries we consider. In this talk I will talk about some restrictions for which such algorithms exist: graphs with bounded degree, tree-like structures, conjunctive queries... We will more specifically consider nowhere dense classes of graphs: What are they? Why is this notion relevant? How to make algorithms from these graph properties?

Location: Humboldt-Universität zu Berlin Institut für Informatik Humboldt-Kabinett (between House 3&4 / 1st Floor [British Reading]) Johann von Neumann-Haus Rudower Chaussee 25 12489 Berlin

Oct 28, 2019 | 02:15 PM

Otfried Cheong (Universität Bayreuth): Convex Covers and Translation Covers

In 1914, Lebesgue asked for a convex set of smallest possible area that can contain a congruent copy of every set of diameter one. The same question can be asked for other families T of planar shapes: What is the convex set of smallest possible area that contains a congruent copy of every element of T? Such a set is then called a convex cover for T, and we will see what smallest-area convex covers for some families of triangles look like. A translation cover for a family T of planar shapes is defined similarly: Z is a translation cover for T if every element of T can be translated into Z. Kakeya's celebrated needle problem, first posed in 1917, turns out to be a question about a smallest-area translation cover. We will see that the generalization of Kakeya's problem to other shapes is also a translation cover problem.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Oct 21, 2019 | 02:15 PM

Vortrag außer der Reihe: Vijay Vazirani (University of California, Irvine): Matching is as Easy as the Decision Problem, in the NC Model Achtung: Dieser Vortrag ist an einem Freitag!

 Is matching in NC, i.e., is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in TCS for over three decades, ever since the discovery of Random NC matching algorithms.  Over the last five years, the TCS community has launched a relentless attack on this question, leading to the discovery of numerous powerful ideas. We give what appears to be the culmination of this line of work: An NC algorithm for finding a minimum weight perfect matching in a general graph with polynomially bounded edge weights, provided it is given an oracle for the decision problem. Consequently, for settling the main open problem, it suffices to obtain an NC algorithm for the decision problem.  We believe this new fact has qualitatively changed the nature of this open problem. Our result builds on the work of Anari and Vazirani (2018), which used planarity of the input graph critically; in fact, in three different ways. Our main challenge was to adapt these steps to general graphs by appropriately trading planarity with the use of the decision oracle. The latter was made possible by the use of several of the ideadiscovered over the last five years. The difficulty of obtaining an NC perfect matching algorithm led researchers to study matching vis-a-vis clever relaxations of the class NC. In this vein, Goldwasser and Grossman (2015) gave a pseudo-deterministic RNC algorithm for finding a perfect matching in a bipartite graph, i.e., an RNC algorithm with the additional requirement that on the same graph, it should return the same (i.e., unique) perfect matching for almost all choices of random bits.  A corollary of our reduction is an analogous algorithm for general graphs. This talk is fully self-contained.  Based on the following joint paper with Nima Anari:  https://arxiv.org/pdf/1901.10387.pdf

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (Ground Floor)

Jul 12, 2019 | 10:15 AM

Anita Liebenau (University of New South Wales, Sydney): Enumerating graphs and other discrete structures by degree sequence

How many d-regular graphs are there on n vertices? What is the probability that G(n,p) has a specific given degree sequence, where G(n,p) is the homogeneous random graph in which every edge is inserted with probability p? Asymptotic formulae for the first question are known when d=o(\sqrt(n)) and when d= \Omega(n). More generally, asymptotic formulae are known for the number of graphs with a given degree sequence, for a wide enough range of degree sequences. From these enumeration formulae one can then deduce asymptotic formulae for the second question. McKay and Wormald showed that the formulae for the sparse case and the dense case can be cast into a common form, and then conjectured in 1990 and 1997 that the same formulae should hold for the gap range. A particular consequence of both conjectures is that the degree sequence of the random graph G(n,p) can be approximated by a sequence of n independent binomial variables Bin(n − 1, p'). In 2017, Nick Wormald and I proved both conjectures. In this talk I will describe the problem and survey some of the earlier methods to showcase the  differences to our new methods. I shall also report on enumeration results of other discrete structures, such as bipartite graphs and hypergraphs, that are obtained by adjusting our methods to those settings.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Jul 08, 2019 | 02:15 PM

Manfred Scheucher (Technische Universität Berlin): On Arrangements of Pseudocircles

Towards a better understanding of arrangements of circles and also to get rid of geometric difficulties, we look at the more general setting of ''arrangements of pseudocircles'' which was first introduced by Grünbaum in the 1970's. An arrangement of pseudocircles is a collection of simple closed curves on the sphere or in the plane such that any two of the curves are either disjoint or intersect in exactly two points, where the two curves cross. In his book, Grünbaum conjectured that every digon-free arrangement of n pairwise intersecting pseudocircles contains at least $2n-4$ triangular cells. We present arrangements to disprove this conjecture and give new bounds on the number of triangular cells for various classes of arrangements. Furthermore, we study the ''circularizability'' of arrangements: it is clear that every arrangement of circles is an arrangement of pseudocircles, however, deciding whether an arrangement of pseudocircles is isomorphic to an arrangement of circles is computationally hard. Using a computer program, we have enumerated all combinatorially different arrangements of up to $7$ pseudocircles. For the class of arrangements of $5$ pseudocircles and for the class of digon-free intersecting arrangements of $6$ pseudocircles, we give a complete classification: we either provide a circle representation or a non-circularizability proof. For these proofs we use incidence theorems like Miquel's and arguments based on continuous deformation, where circles of an assumed circle representation grow or shrink in a controlled way. This talk summarizes results from two articles, which are both joint work with Stefan Felsner: * Arrangements of Pseudocircles: Triangles and Drawings; short version in Proc. GD'17; full version available at arXiv (1708.06449) * Arrangements of Pseudocircles: On Circularizability; short version in Proc. GD'18; full version in DCG: Ricky Pollack Memorial Issue (doi:10.1007/s00454-019-00077-y)

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Jul 01, 2019 | 04:00 PM s.t.

Rekha R. Thomas (University of Washington): Graph Density Inequalities and Sums of Squares

Many results in extremal graph theory can be formulated as inequalities on graph densities. While many inequalites are known, many more are conjectured. A standard tool to establish an inequality is to write the expression whose nonnegativity needs to be certified as a sum of squares. This technique has had many successes but also limitations. In this talk I will describe new restrictions that show that several simple inequalities cannot be certified by sums of squares. These results extend to the powerful frameworks of flag algebras by Razborov and graph algebras by Lovasz and Szegedy. This is joint work with Greg Blekherman, Annie Raymond, and Mohit Singh.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Jul 01, 2019 | 02:15 PM

Simona Boyadzhiyska (Freie Universität Berlin): On counting problems related to (mutually) orthogonal Latin squares

An n×n array with entries in [n] such that each integer appears exactly once in every row and every column is called a Latin square of order n . Two Latin squares L and L' are said to be orthogonal if, for all x,y∈[n], there is a unique pair (i,j) such that L(i,j) = x and L'(i,j) = y; k Latin squares are mutually orthogonal if any two of them are orthogonal. After the question of existence of a combinatorial structure satisfying given properties, a natural and important problem is to determine how many such objects there are. In this talk, we will consider some counting questions related to (mutually) orthogonal Latin squares. We will present an upper bound on the number of ways to extend a set of k mutually orthogonal Latin squares to a set of k+1 mutually orthogonal Latin squares and discuss some applications, comparing the resulting bounds to previously known lower and upper bounds. This talk is based on joint work with Shagnik Das and Tibor Szabó.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Jun 24, 2019 | 04:00 PM s.t.

Emo Welzl (ETH Zürich): Connectivity of Triangulation Flip Graphs in the Plane

In a straight line embedded triangulation of a point set P in the plane, removing an inner edge and - provided the resulting quadrilateral Q is convex - adding the other diagonal is called an edge flip. The flip graph has all triangulations as vertices and a pair of triangulations is adjacent, if they can be obtained from each other by an edge flip. This presentation is towards a better understanding of this graph, with emphasis on its connectivity. It is known that every triangulation allows at least n/2-2 edge flips and we show (n/2-2)-vertex connectivity for flip graphs of all P in general position, n:=|P|. Somewhat stronger, but restricted to P large enough, we show that the vertex connectivity is determined by the minimum degree occurring in the flip graph, i.e. the minimum number of flippable edges in any triangulation of P.  A corresponding result is shown for so-called partial triangulations, i.e. the set of all triangulations of subsets of P which contain all extreme points of P. Here the flip operation is extended to bistellar flips (edge flip, and insertion and removal of an inner vertex of degree three). We prove (n-3)-edge connectedness for all P in general position and (n-3)-vertex connectedness for n large enough ((n-3) is tight, since there is always a partial triangulation which allows exactly n-3 bistellar flips). This matches the situation known (through the secondary polytope) for regular triangulations (i.e. partial triangulations obtained by lifting the points and projecting the lower convex hull). This is joint work with Uli Wagner, IST Austria.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (Ground Floor)

Jun 24, 2019 | 02:15 PM
Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)