Lecture at 14:15, Colloquium at 16:00, every Monday during the teaching period

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

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

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.

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

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ó.

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

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.

Jun 24, 2019 | 02:15 PM

We study the Lonely Runner Conjecture, conceived by Wills in the 1960's: Given positive integers n_1, n_2, ..., n_k, there exists a positive real number t such that for all 1 ≤ j ≤ k the distance of tn_j to the nearest integer is at least 1/(k+1). Continuing a view-obstruction approach by Cusick and recent work by Henze and Malikiosis, our goal is to promote a polyhedral ansatz to the Lonely Runner Conjecture. Our results include geometric proofs of some folklore results that are only implicit in the existing literature, a new family of affirmative instances defined by the parities of the speeds, and geometrically motivated conjectures whose resolution would shed further light on the Lonely Runner Conjecture.

Jun 17, 2019 | 02:15 PM

This highly interdisciplinary conference is motivated by challenges arising in the analysis and the algorithmic treatment of next generation networks. Networks already have a close connection to algorithmic game theory, but we are convinced that future research in this area will benefit from additional geometric insights. Quantum communication networks promise notions of secure multi-partite communication. This international conference - bringing together leading experts in their fields - explores topics in network games, tropical geometry and quantum communication and their interrelation. It is part of the Thematic Einstein Semester of the newly installed MATH+ excellence cluster on application-oriented mathematics within the Berlin research landscape.

Jun 03, 2019 - Jun 07, 2019

A p-centered coloring is a vertex-coloring of a graph G such that every connected subgraph H of G either receives more than p colors or there is a color that appears exactly once in H. The concept was introduced by Nešetřil and Ossona de Mendez as a local condition for measuring sparsity. We prove lower bounds on the p-centered coloring numbers. For outerplanar graphs, we show that their maximum p-centered coloring number is in Theta(p log p). We have examples of graphs of treewidth k needing (p+k choose k) colors, this matches the upper bound of Pilipczuk and Siebertz. We show that planar graphs may require Omega(p^2 log(p)) colors, while all of them admit a p-centered coloring with O(p^3 log(p)) colors. This improves an O(p^19) bound by Pilipczuk and Siebertz.

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

May 27, 2019 | 04:00 PM s.t.

Trivially, the maximum chromatic number of a graph on n vertices is n, and the only graph which achieves this value is the complete graph K_n. It is natural to ask whether this result is "stable", i.e., if n is large, G has n vertices and the chromatic number of G is close to n, must G be close to being a complete graph? It is easy to see that for each c>0, if G has n vertices and chromatic number at least n−c, then it contains a clique whose size is at least n−2c. We will consider the analogous questions for posets and dimension. Now the discussion will really become interesting.

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

May 27, 2019 | 02:15 PM

Probably the most studied invariant in Topological Data Analysis is the homology of a space. The usual approach is to triangulate the space and try to reduce it in order to make the computations more feasible. A common reduction technique is that of collapsing. In a collapsing process we perform a sequence of elementary collapses, where at each step we delete a free face and the unique facet containing it. If we are able to reduce a complex to one of its vertices then we say it is collapsible and its homology is trivial. Collapsibility implies that the space is contractible but the converse is not always true, probably the best known example is the Dunce Hat.We are going to explore the difference between these two concepts and look for minimal examples of contractible non collapsible complexes in each dimension and how often they arise.

May 20, 2019 | 04:00 PM s.t.

This is joint work with Bob MacPherson. We study the configuration space config(n,w) of n non-overlapping disks of unit diameter in an infinite strip of width w. Our main result establishes the rate of growth of the Betti numbers for fixed j and w as n → ∞. We identify three regions in the (j,w) plane exhibiting qualitatively different topological behavior. We describe these regions as (1) a “gas” regime where homology is stable, (2) a “liquid” regime where homology is unstable, and (3) a “solid” regime where homology is trivial. We describe the boundaries between stable, unstable, and trivial homology for every n ≥ 3.

May 20, 2019 | 02:15 PM

We say that a convex body K has the lattice point covering property, if K contains a lattice point of Z^n in any position, i.e., in any translation and rotation of K. In this talk we discuss the lattice point covering property of some regular polygons in dimension 2.

May 13, 2019 | 04:00 PM s.t.

A long-standing open problem, known as Hadwiger’s covering problem, asks what is the smallest natural number N(n) such that every convex body in {\mathbb R}^n can be covered by a union of the interiors of at most N(n) of its translates. In this talk, I will discuss some history of this problem and its close relatives, and present more recent results, including a new general upper bound for N(n).

May 13, 2019 | 02:15 PM

In the Art Gallery Problem we are given a polygon P \subset [0,L]^2 on n vertices and a number k. We want to find a guard set G of size k, such that each point in P is seen by a guard in G. Formally, a guard g sees a point p \in P if the line segment pg is fully contained inside the polygon P. The history and practical findings indicate that irrational coordinates are a "very rare" phenomenon. We give a theoretical explanation. Next to worst case analysis, Smoothed Analysis gained popularity to explain the practical performance of algorithms, even if they perform badly in the worst case. The idea is to study the expected performance on small perturbations of the worst input. The performance is measured in terms of the magnitude \delta of the perturbation and the input size. We consider four different models of perturbation. We show that the expected number of bitsto describe optimal guard positions per guard is logarithmic in the input and the magnitude of the perturbation. This shows from a theoretical perspective that rational guards with small bit-complexity are typical. Note that describing the guard position isthe bottleneck to show NP-membership. The significance of our results is that algebraic methods are not needed to solve the Art Gallery Problem in typical instances. This is the first time an ER-complete problem was analyzed by Smoothed Analysis. This is joint work with Michael Dobbins and Andreas Holmsen.

May 06, 2019 | 04:00 PM s.t.

In the theory of valid inequalities for integer point sets in polyhedra, the traditional, finite-dimensional techniques of polyhedral combinatorics are complemented by infinite-dimensional methods, the study of cut-generating functions. I will give an introduction to these methods and will explain their connection to lattice-free convex bodies. I will present recent results involving inverse semigroups of partial maps, obtained jointly with Robert Hildebrand and Yuan Zhou, and highlight some open questions regarding computability and complexity.

May 06, 2019 | 02:15 PM

In this talk I present a general and versatile algorithmic framework for exhaustively generating a large variety of different combinatorial objects, based on encoding them as permutations, which provides a unified view on many known results and allows us to prove many new ones. In particular, we obtain the following four classical Gray codes as special cases: the Steinhaus-Johnson-Trotter algorithm to generate all permutations of an n-element set by adjacent transpositions; the binary reflected Gray code to generate all n-bit strings by flipping a single bit in each step; the Gray code for generating all n-vertex binary trees by rotations due to Lucas, van Baronaigien, and Ruskey; the Gray code for generating all partitions of an n-element ground set by element exchanges due to Kaye. The first main application of our framework are permutation patterns, yielding new Gray codes for different pattern-avoiding permutations, such as vexillary, skew-merged, X-shaped, separable, Baxter and twisted Baxter permutations etc. We also obtain new Gray codes for five different types of geometric rectangulations, also known as floorplans, which are divisions of a square into n rectangles subject to different restrictions. The second main application of our framework are lattice congruences of the weak order on the symmetric group S_n. Recently, Pilaud and Santos realized all those lattice congruences as (n-1)-dimensional polytopes, called quotientopes, which generalize hypercubes, associahedra, permutahedra etc. Our algorithm generates each of those lattice congruences, by producing a Hamilton path on the skeleton of the corresponding quotientope, yielding a constructive proof that each of these highly symmetric graphs is Hamiltonian. This is joint work with Liz Hartung, Hung P. Hoang, and Aaron Williams.

Apr 29, 2019 | 04:00 PM s.t.

Tope graphs of Complexes of Oriented Matroids fall into the important class of metric graphs called partial cubes. They capture a variety of interesting graphs such as flip graphs of acyclic orientations of a graph, linear extension graphs of a poset, region graphs of hyperplane arrangements to name a few. After a soft introduction into oriented matroids and tope graphs, we give two purely graph theoretical characterizations of tope graphs of Complexes of Oriented Matroids. The first is in terms of a new notion of excluded minors for partial cube, the second is in terms of classical metric properties of certain so-called antipodal subgraphs. Corollaries include a characterization of topes of oriented matroids due to da Silva, another one of Handa, a characterization of lopsided systems due to Lawrence, and an intrinsic characterization of tope graphs of affine oriented matroids. Moreover, we give a polynomial time recognition algorithms for tope graphs, which solves a relatively long standing open question. I will try to furthermore give some perspectives on classical problems as Las Vergnas simplex conjecture in terms of Metric Graph Theory. Based on joint work with H.-J; Bandelt, V. Chepoi, and T. Marc.

Apr 29, 2019 | 02:15 PM

The Plantinga-Vegter algorithm is a subdivision algorithm that produces an isotopic approximation of implicit smooth curves in the plane (and also of surfaces in the three dimensional space). Despite remarkable practical success of the algorithm, little was known about its complexity. The only existing complexity analysis due to Burr, Gao and Tsigaridas provides worst-case bounds that are exponential both in the degree and the bit size of the input polynomial. Despite being tight, this worst-case bound doesn't explain why the algorithm is efficient in practice.In this talk, we show how condition numbers, combined with techniques from geometric functional analysis, help to solve this issue.This is joint work with Alperen A. Ergür and Felipe Cucker.

Apr 15, 2019 | 04:00 PM s.t.

Matrices of nonnegative rank at most r form a semialgebraic set. This semialgebraic set is understood for r=1,2,3. In this talk, I will recall what was previously known about this semialgebraic set and present recent results on the boundaries of the set of matrices of nonnegative rank at most four using notions from the rigidity theory of frameworks. These results are joint work with Robert Krone. In the nonnegative rank three case, all boundaries are trivial or consist of matrices that have only infinitesimally rigid factorizations. For arbitrary nonnegative rank, we give a necessary condition on zero entries of a nonnegative factorization for the factorization to be infinitesimally rigid, and we show that in the case of 5×5 matrices of nonnegative rank four, there exists an infinitesimally rigid realization for every zero pattern that satisfies this necessary condition. However, the nonnegative rank four case is much more complicated than the nonnegative rank three case, and there exist matrices on the boundary that have factorizations that are not infinitesimally rigid. We discuss two such examples.

Apr 15, 2019 | 02:15 PM

Solving systems of polynomial equations is one of the oldest and most important problems in computational mathematics and has many applications in several domains of science and engineering. It is an intrinsically hard problem with complexity at least single exponential in the number of variables. However, in most of the cases, the polynomial systems coming from applications have some kind of structure. For example, several problems in computer-aided design, robotics, computer vision, molecular biology and kinematics involve polynomial systems that are sparse that is, only a few monomials have non-zero coefficients. We focus on exploiting the sparsity of the Newton polytopes of the polynomials to solve the systems faster than the worst case estimates. In this talk, I will present a Gröbner basis approach to solve sparse 0-dimensional systems whose input polynomials have different Newton polytopes. Under regularity assumptions, we can have an explicit combinatorial bound for the complexity of the algorithm. This is joint work with Jean-Charles Faugère and Elias Tsigaridas.

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

I will discuss three unrelated sets of results combining geometry and algorithms. First we will see classes of graphs defined using the intersection of geometric objects in the plane, and discuss classical optimization problems for them. Then we will consider approximation algorithms for the potato peeling problem: find a maximum-area convex body inside a given polygon. The problem amounts to finding a maximum clique in the visibility graph of random samples of points inside the polygon, and results from stochastic geometry are used to bound the size of the samples. Finally, we will discuss the efficient computation of Shapley values for coalitional games defined by the area of usual geometric objects, such as the convex hull or the minimum axis-parallel bounding box.

Feb 11, 2019 | 02:15 PM

A major theme in both extremal and probabilistic combinatorics is to find the appearance thresholds for certain spanning structures. Classical examples of such spanning structures include perfect matchings, Hamilton cycles and H-tilings, where we look for vertex disjoint copies of H covering all the vertices of some host graph G. In this talk we will focus on H-tilings in the case that H is a clique, a natural generalisation of a perfect matching. On the one hand there is the extremal question, how large does the minimum degree of an n-vertex graph G have to be to guarantee the existence of a clique factor in G? On the other hand, there is the probabilistic question. How large does p need to be to almost surely ensure the appearance of a clique factor in the Erdős-Rényi random graph G(n,p)? Optimal answers to these questions were given in two famous papers. The extremal question was answered by Hajnal and Szemerédi in 1970 and the probabilistic question by Johansson, Kahn and Vu in 2008. In this talk we bridge the gap between these two results by approaching the following question which contains the previous questions as special cases. Given an arbitrary graph of some fixed minimum degree, how many random edges need to be added on the same set of vertices to ensure the existence of a clique tiling? We give optimal answers to this question in all cases. Such results are part of a recent research trend studying properties of what is known as the randomly perturbed graph model, introduced by Bohman, Frieze and Martin in 2003. This is joint work with Jie Han and Andrew Treglown.

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

Stanley gave us necessary conditions that f-vectors of simplicial polytopes must satisfy by relating the problem to the hard Lefschetz theorem in algebraic geometry, an insurmountably deep and intimidating theorem in algebraic geometry. McMullen conjectured that these conditions are necessary in general, posing before us the problem of proving the hard Lefschetz theorem beyond what algebraic geometers would dream of. I will talk about the revenge of combinatorics, and in particular discuss how Hall's marriage theorem (or rather, one of its proofs) provides a way to this deep algebraic conjecture. Based on arxiv:1812.10454

Feb 04, 2019 | 02:15 PM

The second theorem of Minkowski on successive minima provides optimal upper and lower bounds on the volume of a symmetric convex body in terms of its successive minima. Motivated by conjectures of Mahler and Makai Jr., we study bounds on the volume of a convex body in terms of the successive minima of its polar body. In this talk, we will show the lower bound in the planar case, and the upper bound in the general case. This talk is based on joint work with Martin Henk.

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

The talk deals with the problem of reconstructing the paths of a set of points over time, where, at each of a finite set of moments in time the current positions of the points in space are only accessible through a small number of their line X-rays. Such problems originate from the demand of particle tracking in plasma physics and can be viewed as constrained version of min-cost-flow and multi assignment problems. (Joint work with A. Alpers)

Jan 28, 2019 | 02:15 PM

The n-cube is the poset obtained by ordering all subsets of {1,2,...,n} by inclusion. A symmetric chain is a sequence of subsets Ak⊆Ak+1⊆…⊆An-k with |Ai|=i for all i=k,…,n-k, and a symmetric chain decomposition, or SCD for short, of the n-cube is a partition of all its elements into symmetric chains. There are several known descriptions of SCDs in the n-cube for any n≥1, going back to works by De Bruijn, Aigner, Kleitman and several others. All those constructions, however, yield the very same SCD. In this talk I will present several new constructions of SCDs in the n-cube. Specifically, we construct five pairwise edge-disjoint SCDs in the n-cube for all n≥90, and four pairwise orthogonal SCDs for all n≥60, where orthogonality is a slightly stronger requirement than edge-disjointness. Specifically, two SCDs are called orthogonal if any two chains intersect in at most a single element, except the two longest chains, which may only intersect in the unique minimal and maximal element (the empty set and the full set). This improves the previous best lower bound of three orthogonal SCDs due to Spink, and is another step towards an old problem of Shearer and Kleitman from the 1970s, who conjectured that the n-cube has ⌊n/2⌋+1 pairwise orthogonal SCDs. We also use our constructions to prove some new results on the central levels problem, a far-ranging generalization of the well-known middle two levels conjecture (now theorem), on Hamilton cycles in subgraphs of the (2n+1)-cube induced by an even number of levels around the middle. Specifically, we prove that there is a Hamilton cycle through the middle four levels of the (2n+1)-cube, and a cycle factor through any even number of levels around the middle of the (2n+1)-cube. This talk is based on two papers, jointly with Sven Jäger, Petr Gregor, Joe Sawada, and Kaja Wille (ICALP 2018), and with Karl Däubel, Sven Jäger, and Manfred Scheucher, respectively.

Jan 21, 2019 | 04:00 PM s.t.

A numerical semigroup is a subset of the positive integers (N) together with 0, closed under addition, and with a finite complement in N∪{0}. The number of gaps is its genus. Numerical semigroups arise in algebraic geometry, coding theory, privacy models, and in musical analysis. It has been shown that the sequence counting the number of semigroups of each given genus g, denoted (ng)g≥0, has a Fibonacci-like asymptotic behavior. It is still not proved that, for each g, ng+2 ≥ ng+1 + ng or, even more simple, ng+1 ≥ ng. We will explain some classical problems on numerical semigroups as well as some of their applications to other fields and we will explain the approach of counting semigroups by means of trees.

Jan 21, 2019 | 02:15 PM

Motivated by extreme value theory, max-linear graphical models have been recently introduced and studied as an alternative to the classical Gaussian or discrete distributions used in graphical modeling. We present max-linear models naturally in the framework of tropical geometry. This perspective allows us to shed light on some known results and to prove others with algebraic techniques. In particular, we rephrase parameter estimation for max-linear models in terms of cones in the tropical eigenspace fan. This is joint work with Claudia Klüppelberg, Steffen Lauritzen and Ngoc Tran.

Jan 14, 2019 | 04:00 PM s.t.

An independent transversal (IT) in a vertex-partitioned graph G is an independent set in G consisting of one vertex in each partition class. There are several known criteria that guarantee the existence of an IT, of the following general form: the graph G has an IT unless the subgraph GS of G, induced by the union of some subset S of vertex classes, has a small dominating set. These criteria have been used over the years to solve many combinatorial problems. The known proofs of these IT theorems do not give efficient algorithms for actually finding an IT or a subset S of classes such that GS has a small dominating set. Here we present appropriate weakenings of such results that do have effective proofs. These result in algorithmic versions of many of the original applications of IT theorems. We will discuss a few of these here, including hitting sets for maximum cliques, circular edge colouring of bridgeless cubic graphs, and hypergraph matching problems.

Jan 14, 2019 | 02:15 PM

In the well-known Steiner Tree problem, the objective is to connect a set of terminals at the least total cost. We can further constrain the problem by specifying upper bounds for the distance of each terminal to a chosen root terminal. Further, using the Lagrangianr elaxation of this restriction, we can penalize large distances in the objective function rather than applying strict distance constraints. We arrive at a special case of the so-called Cost-Distance Steiner Tree Problem in which we have a single weight function on the edges. In this talk, I will present several results from my master's thesis that concern the Cost-Distance Steiner Tree Problem. The NP-hardness of the Cost-Distance Steiner Tree Problem trivially follows from the fact that the regular Steiner Tree problem is the special case where we set demand weights (Lagrange multipliers) of the terminals to zero. I therefore proceed to prove that the problem remains NP-hard in three restricted cases that do not contain the regular Steiner Tree Problem as a special case. Then I improve on a previous constant-factor approximation for the single-weighted case by using a hybrid method of an approximate Steiner tree with a shortest-path tree replacing sections of the tree where path segments are used by many terminals with demand weights summing to higher than a tunable threshold. I also use a similar approach to extend Arora's dynamic-programming method for the two-dimensional geometric Steiner Tree Problem to the case with the penalizing terms in the objective function.

Jan 07, 2019 | 04:00 PM s.t.

In this talk we will look at a new variant of the polynomial method which was first used to prove that sets avoiding 3-term arithmetic progressions in groups like Z4n (Croot, Lev and myself) and Z3n (Ellenberg and Gijswijt) are exponentially small (compared to the size of the group).We will discuss lower and upper bounds for the size of the extremal subsets, including some recent bounds found by Elsholtz and myself. We will also mention some further applications of the method, for instance, the solution of the Erdős-Szemerédi sunflower conjecture.

Jan 07, 2019 | 02:15 PM

In 2007, when the credit crisis began, the Bank of England approached the economist Paul Klemperer with the need of a new auction design that would enable them to give liquidity to all banks in an economically efficient way. Since then, Klemperer’s Product-Mix Auction design became more and more relevant, with particular interest in when competitive equilibrium exists, that is, when a set of (indivisible) goods can be split such that exactly one bid of each bidder is fulfilled. Originally being a question of economics, this can be translated into a question of specific lattice polytopes that rely on underlying graphs. I will present the Product-Mix Auction setting, the translation to polytopes and first results on when competitive equilibrium exists.

Dec 17, 2018 | 04:00 PM s.t.

The combinatorial properties much-loved Erdős-Rényi random graph G(n,p), which has n vertices and whose edges are present independently with probability p, have been comprehensively studied in the decades since its introduction. In recent years, much research has been devoted to the randomly perturbed graph model, introduced in 2003 by Bohman, Frieze and Martin. In this talk we shall present and motivate this new model of random graphs, and then focus on the Ramsey properties of these randomly perturbed graphs. More precisely, given a pair of graphs (F,H), we ask how many random edges must be added to a dense graph G to ensure that any two-colouring of the edges of the perturbed graph has either a red copy of F or a blue copy of G. This question was first studied in 2006 by Krivelevich, Sudakov and Tetali, who answered it in the case of F being a triangle and H being a clique. We generalise these results, considering pairs of larger cliques, and, should the audience be willing (but even otherwise), shall take a quick look at some of the ideas required in our proofs. This is joint work with Andrew Treglown (Birmingham).

Dec 17, 2018 | 02:15 PM

In a two-colouring of the edges of the complete graph on the natural numbers, what is the densest monochromatic infinite path that we can always find? We measure the density of a path by the upper asymptotic density of its vertex set. This question was first studied by Erdös and Galvin, who proved that the best density is between 2/3 and 8/9. In this talk we settle this question by proving that we can always find a monochromatic path of upper density at least (12+sqrt(8))/17=0.87226…, and constructing a two-colouring in which no denser path exists. This represents joint work with Jan Corsten, Louis DeBiasio and Richard Lang.

Dec 10, 2018 | 04:00 PM s.t.

Progress in satisfiability (SAT) solving has enabled answering long-standing open questions in mathematics completely automatically resulting in clever though potentially gigantic proofs. We illustrate the success of this approach by presenting the solution of the Boolean Pythagorean triples problem. We also produced and validated a proof of the solution, which has been called the ``largest math proof ever''. The enormous size of the proof is not important. In fact a shorter proof would have been preferable. However, the size shows that automated tools combined with super computing facilitate solving bigger problems. Moreover, the proof of 200 terabytes can now be validated using highly trustworthy systems, demonstrating that we can check the correctness of proofs no matter their size.

Dec 10, 2018 | 02:15 PM

Two incidences (u,e) and (v,f) of vertices u, v and edges e, f (respectively) are adjacent if u=v, or e=f, or uv is one of edges e, f. An incidence coloring of a graph G is a coloring of its incidences such that adjacent incidences have distinct colors. We show that every graph of maximal degree 4 has an incidence coloring with 7 colors. Furthermore, we present sufficient conditions for Cartesian product graphs to have incidence colorings with Delta+2 colors where Delta is the maximal degree. In particular, we confirm a conjecture of Pai et al. on incidence colorings of hypercubes. Joint work with B. Lužar and R. Soták.

Dec 03, 2018 | 04:00 PM s.t.

Binary search trees (BSTs) and heaps are perhaps the simplest implementations of the dictionary and the priority queue data types. They are among the most extensively studied structures in computer science, yet, many basic questions about them remain open. What is the best strategy for updating a BST in response to queries? Is there a single strategy that is optimal for every possible scenario? Are self-adjusting trees ("splay trees", Sleator, Tarjan, 1983) optimal? In which cases can we improve upon the logarithmic worst-case cost per operation? Our understanding of heaps is even more limited. Fibonacci heaps (and their relatives) are theoretically optimal in a worst-case sense, but they perform operations outside the "pure" comparison-based heap model (in addition to being complicated in practice). Is there a simple, "self-adjusting" alternative to Fibonacci heaps? Is there, by analogy to BSTs, a heap that can adapt to regularities in the input? Are the two problems related? In my talk I will present some old and new results pertaining to this family of questions.

Dec 03, 2018 | 02:15 PM

The notions of bounded expansion and nowhere denseness capture uniform sparseness of graph classes and render various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce structurally bounded expansion and structurally nowhere dense graph classes, dfined as first-order interpretations of bounded expansion and nowhere dense graph classes. As a first step towards their algorithmic treatment, we provide a characterization of structurally bounded expansion classes via low shrubdepth decompositions, a dense analogue of low treedepth decompositions. We prove that structurally nowhere dense graph classes are vc-minimal.

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

Nov 26, 2018 | 04:00 PM s.t.

While most NP-hard graph problems remain NP-hard when restricted to planar graphs, they become somewhat simpler: they often admit algorithms with running time exponential in the square root of the size of the graph (or some other meaningful parameter). This behavior has been dubbed "the square root phenomenon". For many problems, such an algorithm follows from the theory of bidimensionality relying on a linear dependency on the size of the largest grid minor and treewidth of a planar graph. In recent years we have seen a number of other algorithmic techniques, significantly extending the boundary of the applicability of the "square root phenomenon". In my talk I will survey this area and highlight main algorithmic approaches.

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

Nov 26, 2018 | 02:15 PM

The associahedron has a natural extension called the multiassociahedron. It is a vertex-decomposable simplicial sphere (in other words, a "combinatorially nice" sphere). Since at least 2003, people tried to construct simplicial polytopes, whose boundary is this simplicial complex, with limited success. In this talk, I will reveal (at least) three combinatorial "known-to-be-challenging" computational problems which should be indispensably faced to solve this problem.

Nov 19, 2018 | 04:00 PM s.t.

Picture yourself in a committee numerically evaluating a scientific proposal that you find worth funding: A rating of "0" means "easily achievable but not at all innovative", whereas "1" means "very innovative but totally unachievable". In both cases, funding is not recommended. In contrast, "1/2" means "innovative and achievable", in other words: worth funding. All intermediate values are possible. Any rating that is closer to "1/2" than to "1/4" and "3/4" is considered a vote for funding. The proposal passes if 50% of the members support funding, i.e., rate the proposal between "1/2 - 1/8" and "1/2 + 1/8". Now, there are 10 meetings ahead of you. You have an idea how the opinions of the committee members develop. How should your statements look like in the meetings one through ten if you want to have eventually as many supporters of the proposal as possible? This is an instance of the "Optimal Diplomacy Problem" (ODP), introduced by Hegselmann, König, Kurz, Niemann, and Rambau in 2010, published in 2015. How do opinions interact? How is the dynamics of opinions modeled mathematically? What does it mean to "influence others" in this dynamical system? How difficult is it to find optimal diplomacies? How can one compute or at least narrow down optimal diplomacies? What happens if not all informations about committee members are known to the diplomat? In this talk we will discuss our findings, techniques, and open questions based on the arguably most influential model: the Bounded-Confidence model by Hegselmann and Krause. We draw on joint work with Andreas Deuerling, Rainer Hegselmann, Stefan König, Julia Kinkel, Sascha Kurz, and Christoph Niemann.

Nov 19, 2018 | 02:15 PM

Kernelization is a key concept in fixed-parameter algorithmics for polynomial-time preprocessing of NP-hard problems. Herein one seeks to preprocess any instance of a parameterized problem with parameter k to an “equivalent” instance (the so-called (problem) kernel) with size upper-bounded by some function (preferably by some polynomial) in k. Ten years ago, with the development of the so-called composition technique, first NP-hard parameterized problems were proven to presumably admit no polynomial-size problem kernel. Since then the line of Research concerning "limits of kernelization" received a lot of attention. We contribute to this line and present a new technique exploiting triangle-based fractal structures (so called T-fractals) for extending the range of applicability of compositions. Our technique makes it possible to prove new no-polynomial-kernel results for a number of graph problems dealing with some sort of cuts, hereby answering an open question stated in 2009. Our T-fractals---due to their fractal structure---admit easy-to-prove useful properties exploitable for constructing compositions. They also apply for planar as well as directed variants of the basic problems and also apply to both edge and vertex-deletion problems. This is joint work with Danny Hermelin, André Nichterlein, and Rolf Niedermeier. (Journal version appeared in SIAM Journal on Discrete Mathematics 2018.)

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

Nov 12, 2018 | 04:00 PM s.t.

In this lecture I will give an introduction to algebraic and semi-algebraic methods for proving the unsatisfiability of systems of real polynomial equations over the Boolean hypercube. The main goal of this talk is to compare the relative strength of these approaches using methods from proof complexity. On the one hand, I will focus on the static semi-algebraic proof systems Sherali-Adams and sum-of-squares (a.k.a. Lasserre), which are based on linear and semi-definite programming relaxations. On the other hand, I will discuss polynomial calculus, which is a dynamic algebraic proof system that models Gröbner basis computations. I am going to present two recent results on the relative strength between algebraic and semi-algebraic proof systems:¹ The first result is that sum-of-squares simulates polynomial calculus: any polynomial calculus refutation of degree d can be transformed into a sum-of-squares refutation of degree 2d and only polynomial increase in size. In contrast, the second result shows that this is not the case for Sherali-Adams: there are systems of polynomial equations that have polynomial calculus refutations of degree 3 and polynomial size, but require Sherali-Adams refutations of large degree and exponential size. ¹) this work was presented at STACS 2018; a preprint is available at https://eccc.weizmann.ac.il/report/2017/154/

Nov 12, 2018 | 02:15 PM

Network analysis defines a number of centrality measures to identify the most central nodes in a network. Fast computation of those measures is a major challenge in algorithmic network analysis. Aside from closeness and betweenness, Katz centrality is one of the established centrality measures. We consider the problem of computing rankings for Katz centrality. In particular, we propose upper and lower bounds on the Katz score of a given node. While previous approaches relied on numerical approximation or heuristics to compute Katz centrality rankings, we construct an algorithm that iteratively improves those upper and lower bounds until a correct Katz ranking is obtained. For a certain class of inputs, this yields an optimal algorithm for Katz ranking computation. Furthermore, Experiments demonstrate that our algorithm outperforms both numerical approaches and heuristics with speedups between 1.5x and 3.5x, depending on the desired quality guarantees. Specifically, we provide efficient parallel CPU and GPU implementations of the algorithms that enable near real-time Katz centrality computation for graphs with hundreds of millions of nodes in fractions of seconds.

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

Nov 05, 2018 | 04:00 PM s.t.

Network centrality measures indicate the importance of nodes (or edges) in a network. In this talk we will discuss a few popular measures and algorithms for computing complete or partial node rankings based on these measures. These algorithms are implemented in NetworKit, an open-source framework for large-scale network analysis, on which we provide an overview, too. One focus of the talk will be on techniques for speeding up a greedy (1-1/e)-approximation algorithm for the NP-hard group closeness centrality problem. Compared to a straightforward implementation, our approach is orders of magnitude faster and, compared to a heuristic proposed by Chen et al., we always find a solution with better quality in a comparable running time in our experiments. Our method Greedy++ allows us to approximate the group with maximum closeness centrality on networks with up to hundreds of millions of edges in minutes or at most a few hours. In a comparison with the optimum, our experiments show that the solution found by Greedy++ is actually much better than the theoretical guarantee.

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

Nov 05, 2018 | 02:15 PM

For several graph classes without long induced paths there exists a finite forbidden subgraph characterization for k-colourability. Such a finite set of minimal obstructions allows to provide a “no-certificate" which proves that a graph is not k-colourable. We prove that there are only finitely many 4-critical P6-free graphs, and give the complete list that consists of 24 graphs. In particular, we obtain a certifying algorithm for 3-colouring P6-free graphs, which solves an open problem posed by Golovach et al. (Here, P6 denotes the induced path on six vertices.) Our result leads to the following dichotomy theorem: if H is a connected graph, then there are finitely many 4-critical H-free graphs if and only if H is a subgraph of P6. This answers a question of Seymour. The proof of our main result involves two distinct automatic proofs, and an extensive structural analysis by hand. In this talk we will mainly focus on the algorithmic results by presenting a new algorithm for generating all minimal forbidden subgraphs to k-colourability for given graph classes. This algorithm (combined with new theoretical results) has been successfully applied to fully characterise all forbidden subgraphs for k-colourability for various classes of graphs without long induced paths. (This is joint work with Maria Chudnovsky, Oliver Schaudt and Mingxian Zhong.)

Oct 29, 2018 | 04:00 PM s.t.

Perfect graphs are important objects in graph theory. The perfect graphs include many important families of graphs, and serve to unify results relating colorings and cliques in those families. One of the most famous and most important results is the strong perfect graph theorem conjectured by Claude Berge and proved by Chudnovsky, Robertson and Thomas. This theorem characterizes perfect graphs. Our interest is to give other characterizations of perfect graphs. In this talk, we construct several lattice polytopes arising from a finite simple graph and characterize when the graph is perfect in terms of the lattice polytopes. This talk is based on joint work with Takayuki Hibi and Hidefumi Ohsugi.

Oct 22, 2018 | 04:00 PM s.t.

As we tell our undergraduates, if K is a field, then there are a great number of different ways to describe a linear subspace of K^n. If the base is an algebraic object with less structure than a field, linear algebra becomes more subtle, and some of these descriptions cease to agree. One such setting is tropical geometry. Tropical geometers have reached consensus as to what the "correct" notion of tropical linear subspace is (one way to get it is by a vector of determinants). My subject will be one of the "wrong" descriptions, namely row spaces of matrices, which only produces a subset of the tropical linear spaces. Applications include generalisations of Mason's results from the '70s on presentations of transversal matroids, and a construction in the new area of tropical ideal theory. This work is variously joint with Felipe Rinc\'on, Jorge Alberto Olarte, and Jeffrey and Noah Giansiracusa.

Oct 22, 2018 | 02:15 PM

There has recently been a lot of interplay between extremal graph theory and the theory of graph limits. After a brief survey of the theory of dense graph limits, we focus on exploring a link between Sidorenko's Conjecture, one of the most prominent open problems in extremal graph theory, and weakly norming graphs, one of the concepts studied in the theory of graph limits. Sidorenko's Conjecture asserts that every bipartite graph H has the Sidorenko property, i.e., a quasirandom graph minimizes the density of H among all graphs with the same edge density. We are interested in a stronger property, which we call the step Sidorenko property. We relate this property to weakly norming graphs and use our results to construct a bipartite edge-transitive graph that is not weakly norming - this answers a question of Hatami [Israel J. Math. 175 (2010), 125-150]. The talk is based on joint work with Taisa Martins, Peter Pal Pach and Marcin Wrochna.

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

Oct 08, 2018 | 02:00 PM s.t.

For positive integers N and r >= 2, an r-monotone coloring of r-tuples from [N] is a 2-coloring by -1 and +1 that is monotone on the lexicographically ordered sequence of r-tuples of every (r+1)-tuple from [N]. Let ORS(n;r) be the minimum N such that every r-monotone coloring of r tuples from [N] contains n elements with all r-tuples of the same color. For every r >= 3, it is known that ORS(n;r) is bounded from above by a tower function of height r-2 with O(n) on the top. The Erdős--Szekeres Lemma and the Erdős--Szekeres Theorem imply ORS(n;2)=(n-1)^2+1 and ORS(n;3) = ((2n-4) choose (n-2))+1, respectively. It follows from a result of Eliáš and Matoušek that ORS (n;4) grows as o tower of height 2. We show that ORS(n;r) grows at least as a tower of height r-2 for every r >= 3. This, in particular, solves an open problem posed by Eliáš and Matoušek and by Moshkovitz and Shapira. Using two geometric interpretations of monotone colorings, we show connections between estimating ORS(n;r) and two Ramsey-type problems that have been recently considered by several researchers. We also prove asymptotically tight estimates on the number of r-monotone colorings.

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

Jul 16, 2018 | 04:00 PM

We consider random simplicial complexes that are generated from the binomial random hypergraphs by taking the downward-closure. We determine when all cohomology groups with coefficients in F_2 vanish. This is joint work with Oliver Cooley, Nicola Del Giudice, and Philipp Spruessel.

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

Jul 16, 2018 | 02:15 PM

Most computer scientists and discrete mathematicians are familiar with computational complexity due to the famous P = NP conjecture. Some researchers have a more thorough understanding of the classes P, NP, and PSPACE since problems in logic, graph theory, and combinatorial optimization are often classified by their relationship to one of these classes. More recently, these concepts have found a wider audience through their application to puzzles and games. For example, it is known that the number puzzle Sudoku is NP-complete, whereas the box pushing game Sokoban is PSPACE-complete. In this talk we establish the computational complexity of several puzzles and games. We prove that two new paper and pencil puzzles are NP-complete. These puzzles are called Pencils and Sto-Stone, and were created by the Japanese publisher Nikoli that popularized Sudoku. We then prove that several puzzles that have been implemented as video games are PSPACE-complete. These games include a row shifting puzzle called MazezaM, a turnstile puzzle for the Nintendo Game Boy called Kwirk, and a puzzle called Switches that was invented by undergraduate student Jonathan Gabor while he was attending high school. Our reductions use conventional approaches such as Boolean Satisfiability, as well as some less conventional tools including Gray Codes, and the new Constraint Logic model pioneered by Hearn and Demaine in their influential textbook "Games, Puzzles, and Computation". The talk aims to be accessible to a wide audience, and hopes to encourage researchers to seek similar results for problems (or puzzles!) that are close to them. Most of the new results consist of joint work with undergraduate students at Bard College at Simon's Rock.

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

Jul 09, 2018 | 04:00 PM

Matrix rank is well-known to be multiplicative under the Kronecker product, additive under the direct sum, normalised on identity matrices and non-increasing under multiplying from the left and from the right by any matrices. In fact, matrix rank is the only real matrix parameter with these four properties. In 1986 Strassen proposed to study the extension to tensors: find all maps from k-tensors to the reals that are multiplicative under the tensor Kronecker product, additive under the direct sum, normalized on diagonal tensors, and non-increasing under acting with linear maps on the k tensor factors. Strassen called the collection of these maps the "asymptotic spectrum of k-tensors". Strassen proved that understanding the asymptotic spectrum implies understanding the asymptotic relations among tensors, including the asymptotic rank. In particular, knowing the asymptotic spectrum means knowing the arithmetic complexity of matrix multiplication, a central problem in algebraic complexity theory.I will give an overview of known elements in the asymptotic spectrum of tensors, including our recent construction which is based on information theory and moment polytopes. This recent construction is joint work with Matthias Christandl and Peter Vrana.Then I will introduce the analogous object in graph theory: the asymptotic spectrum of graphs. I will explain the relation to Shannon capacity and give an overview of known elements in the asymptotic spectrum of graphs.

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

Jul 09, 2018 | 02:15 PM

Recently, Balletti and I proved that for the h^*-polynomial h_0^*+h_1^*t+... of a lattice polytope, if we assume h_3^*=0, then (h_1^*, h_2^*) satisfies (i) h_2^*=0; or (ii) h_1^* \leq 3h_2^* + 3; or (iii) (h_1^*,h_2^*)=(7,1). These conditions derive from Scott's theorem (1976), who characterized the possible h^*-polynomials of 2-dimensional lattice polytopes, and Scott's theorem is also essentially valid for lattice polytopes with degree at most 2 (Treutlein (2010)). On the other hand, we proved that it also holds under the assumption h_3^*=0. Since the assumption h_3^*=0 is independent of both dimension and degree of polytopes, we call the conditions (i), (ii), (iii) universal. In this talk, towards finding a new universal condition, we investigate the possibility for the polynomial h_0^*+h_1^*t+... to be the h^*-polynomial of some lattice polytope under the assumption that some of h_i^*'s vanish.

Location: Freie Universität Berlin Institut für Mathematik Arnimallee 2 14195 Berlin Seminar Room

Jul 05, 2018 | 02:15 PM

The study of realization spaces of convex polytopes is one of the oldest subjects in Polytope Theory. Most likely, it goes back to Legendre (1794). A lot of progress took place since that time. However, many questions remained open. In general, computing the dimension of the realization space $\mathcal{R}(P)$ of a d-polytope $P$ is hard, even for $d = 4$, as shown by Mnëv (1988) and Richter-Gebert (1996).In this presentation, we will discuss two criteria to determine the dimension of the realization space, and use them to show that $\dim \mathcal{R}(P) = f_1(P) + 6$ for a 3-polytope $P$, and $\dim \mathcal{R}(P) = df_{d-1}(P)$ (resp. $\dim \mathcal{R}(P) = df_0(P)$ ) for a simple (resp. simplicial) $d$-polytope $P$. We will also discuss the realization spaces of some interesting 2-simple 2-simplicial 4-polytopes. Namely, we will consider the realization space of the 24-cell and of a 2s2s polytope with 12 vertices which was found by Miyata (2011), and give a better bound for/determine its dimension.

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

Jul 02, 2018 | 04:00 PM

We describe some recent developments in treewidth-based algorithms for knots, which exploit the structure of the underlying 4-valent planar graph. In particular, we show how these led to the first general sub-exponential-time algorithm for the HOMFLY-PT polynomial, and we describe some recent progress on parameterised algorithms for unknot recognition.

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

Jul 02, 2018 | 02:15 PM

A famous and wide-open problem, going back to at least the early 1970's, concerns the classification of chromatic polynomials of graphs. Toward this classification problem, one may ask for necessary inequalities among the coefficients of a chromatic polynomial, and we contribute one such set of inequalities when a chromatic polynomial $\chi_G(n) = \chi^*_0 \binom {n+d} d + \chi^*_1 \binom {n+d-1} d + \dots + \chi^*_d \binom n d$ is written in terms of a binomial-coefficient basis. More precisely, we prove that $\chi^*_{d-2}+\chi^*_{d-3}+\dots+\chi^*_{d-j-1} \ \ge \ \chi^*_1+\chi^*_2+\dots+\chi^*_j $, for $1 \le j \le \lfloor \frac{ d }{ 2 } \rfloor - 1$. A similar result holds for flow polynomials enumerating either modular or integral nowhere-zero flows of a graph. Our theorems follow from connections among chromatic, flow, order, and Ehrhart polynomials, and the fact that the latter satisfy a decomposition formula into symmetric polynomials due to Stapledon. (This is joint work with Emerson Le\'on.)

Jun 25, 2018 | 04:00 PM

We introduce a family of polytopes, called primitive zonotopes, which can be seen as a generalization of the permutahedron of type $B_d$. We discuss connections to the largest diameter of lattice polytopes and to the computational complexity of multicriteria matroid optimization. Complexity results and open questions are also presented. In particular, we answer a question raised in 1986 by Colbourn, Kocay, and Stinson by showing that deciding whether a given sequence is the degree sequence of a 3-hypergraph is computationally prohibitive. Based on joint works with Asaf Levin (Technion), George Manoussakis (Ben Gurion), Syed Meesum (IMSc Chennai), Shmuel Onn (Technion), and Lionel Pounin (Paris XIII).

Jun 25, 2018 | 02:15 PM

In this talk, I will show how techniques from Combinatorial Optimization and Combinatorics can be leveraged to achieve progress on a well-known question in Integer Programming, namely how to solve integer linear programs (ILPs) with bounded subdeterminants. More precisely, I will present an efficient (even strongly polynomial) algorithm to solve ILPs defined by a constraint matrix whose subdeterminants are all within {-2,-1,0,1,2}. This problem class naturally extends the well-known class of ILPs with a totally unimodular (TU) constraint matrix, i.e., where subdeterminants are within {-1,0,1}, and captures some open problems. We employ a variety of techniques common in Combinatorial Optimization, including polyhedral techniques, matroids, and submodular functions. In particular, using a polyhedral result of Veselov and Chirkov, we reduce the problem to a combinatorial one with a so-called parity constraint. We then show how a seminal, purely combinatorial result of Seymour on decomposing TU matrices, which is tightly related to regular matroids and was originally developed in this context, can be used algorithmically to break the problem into smaller ones. Finally, these smaller problems are amenable to combinatorial optimization techniques like parity-constrained submodular minimization. Additionally, I will highlight some of the many open problems in this field and discuss recent related results.

Jun 18, 2018 | 02:15 PM

The cage problem asks for the smallest number c(k, g) of vertices in a k-regular graph of girth g. The (k, g)-graphs which have c(k, g) vertices are known as cages. While cages are known to exist for all integers k > 1 and g > 2, an explicit construction is known only for some small values of k, g and three infinite families for which g is 6, 8 or 12 and k − 1 is a prime power: corresponding to the generalized g/2-gons of order k − 1. To improve the upper bounds on c(k, 6), c(k, 8) and c(k, 12), when k - 1 is not a prime power, one of the main techniques that has been used so far is to construct small (k, g) graphs by picking a prime power q ≥ k and then finding a small k-regular subgraph of the incidence graph of a generalized g/2-gon of order q. In this talk I will present new constructions in generalized quadrangles and hexagons which improve the known upper bound on c(k, 8) when k = p^{2h} and c(k, 12) when k = p^h, where p is an arbitrary prime. Moreover, we will see a spectral lower bound on the number of vertices in a k-regular induced subgraph of an arbitrary regular graph, which in particular will prove the optimality of a known construction in projective planes. (Joint work with John Bamberg and Gordon Royle)

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin room 005 (ground floor)

Jun 11, 2018 | 04:00 PM s.t.

In 1967, F. Arthur Sherk gave a simple proof that the finite metric planes (of Bachmann and Schmidt) are precisely the affine planes of odd order. Moreover, Sherk’s proof holds for a more general class of incidence structures that do not involve the ‘three-reflection theorem’ whatsoever, and thus yields a beautiful characterisation of the finite affine planes of odd order. By relaxing the first of Sherk’s axioms to ‘every pair of points lies on at most one line’, we can study what we call partial Sherk planes. In this talk, we outline our characterisation of these incidence structures as Bruck nets, in the same vein as Sherk’s result, and what it means for connected combinatorial objects such as mutually orthogonal latin squares. (Joint work with Joanna Fawcett and Jesse Lansdown)

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin room 005 (ground floor)

Jun 11, 2018 | 02:15 PM

From Kalai's classic paper generalizing Cayley's tree-enumeration formula to simplicial complexes, it is known that simplicial complexes on a small number of vertices can have enormous torsion in homology. Moreover, in a random setting one may find instances of this phenomenon such as, for example, a 3-dimensional simplicial complex on 30 vertices with the torsion subgroup of the second homology group having order larger than 10^82. In this talk I will discuss the problem of explicitly constructing such complexes. In particular, I will discuss my work to use the probabilistic method to construct optimally small (up to a constant factor from a known lower bound) simplicial complexes with prescribed torsion in homology. I will also discuss an application of this work to the problem of counting homotopy types of simplicial complexes.

Jun 04, 2018 | 02:15 PM

May 28, 2018 | 04:01 PM s.t.

In the Steiner Tree problem, a set of terminal vertices in an edge-weighted graph needs to be connected in the cheapest possible way. This problem has been extensively studied from the viewpoint of approximation and also parametrization. In particular, on the one hand, Steiner Tree is known to be APX-hard, and on the other hand, it is W[2]-hard if parameterized by the number of non-terminals (Steiner vertices) in the optimum solution. In contrast to this, we give an efficient parameterized approximation scheme (EPAS), which circumvents both hardness results. Moreover, our methods imply the existence of a polynomial size approximate kernelization scheme (PSAKS) for the considered parameter. In the Directed Steiner Network problem we are given an arc-weighted digraph G, a set of terminals T, and an (unweighted) directed request graph R with V(R)=T. Our task is to output a subgraph H of G of the minimum cost such that there is a directed path from s to t in H for all arcs st of R. It is known that the problem can be solved in time |V(G)|O(|A(R)|) [Feldman&Ruhl, SIAM J. Comput. 2006] and cannot be solved in time |V(G)|o(|A(R)|) even if G is planar, unless Exponential-Time Hypothesis (ETH) fails [Chitnis et al., SODA 2014]. However, the reduction (and other reductions showing hardness of the problem) only shows that the problem cannot be solved in time |V(G)|o(|T|), unless ETH fails. Therefore, there is a significant gap in the complexity with respect to |T| in the exponent. We show that Directed Steiner Network is solvable in time f(|T|) · |V(G)| O(cg · |T|), where cg is a constant depending solely on the genus g of G and f is a computable function.

May 28, 2018 | 04:00 PM s.t.

In the k-Set Packing problem we are given a universe and a family of its subsets, where each of the subsets has size at most k. The goal is to select a maximum number of sets from the family which are pairwise disjoint. It is a well known NP-hard problem, that has been studied from the approximation perspective since the 80's. During the talk I will describe the history of progress on both the weighted and unweighted variants of the problem, with an exposition of methods used to obtain the best known approximation algorithms mostly involving local search based routines.

May 28, 2018 | 02:15 PM