Facets of Complexity Monday Lectures

Christoph Hertrich Johann-Wolfgang-Goethe-Universität Frankfurt

(Old and New) Facets of Neural Network Complexity

Abstract.

How to use discrete mathematics and theoretical computer science to understand neural networks? Guided by this question, I will focus on neural networks with rectified linear unit (ReLU) activations, a standard model and important building block in modern machine learning pipelines. The functions represented by such networks are continuous and piecewise linear. But how does the set of representable functions depend on the architecture? And how difficult is it to train such networks to optimality? In my talk I will answer fundamental questions like these using methods from polyhedral geometry, combinatorial optimization, and complexity theory. This stream of research was started during my doctorate within 'Facets of Complexity' and carried much further since then.

Raphael Steiner ETH Zürich

Shortest paths on combinatorial polytopes: Hardness and approximation

Abstract.

I will present some of my joint work with Jean Cardinal on the complexity of computing and approximating shortest paths in the skeleton of a combinatorially defined polytope. In particular, I will discuss proofs for the inapproximability of finding shortest paths on the skeleton of perfect matching polytopes, and of polymatroids, and discuss various related context and problems in which our work is embedded.

Anand Srivastav Kiel

Recent Advances in the Maker Breaker Subgraph Game

Abstract.

The triangle game introduced by Chvátal and Erdős (1978) is one of the old and famous combinatorial games. For n, q ∈ N, the (n,q)-triangle game is played by two players, called Maker and Breaker, on the complete graph K_n .Alternately Maker claims one edge and thereafter Breaker claims q edges of the graph. Maker wins the game if he can claim all three edges of a triangle. Otherwise Breaker wins. Chvátal and Erdős (1978) proved that for q < sqrt(n/2), Maker has a winning strategy, while for q > 2 sqrt(n), Breaker wins. So, the threshold bias must be in the interval [sqrt(1/2)sqrt(n) , 2 sqrt(n)].Since then, the problem of finding the exact constant (and an associated Breaker strategy) for the threshold bias of the triangle game has been one of the interesting open problems in combinatorial game theory. In fact, the constant is not known for any graph with a cycle and we do not even know if such a constant exists. Balogh and Samotij (2011) slightly improved the Chvátal-Erdős constant for Breaker’s winning strategy from 2 to 1.935 with a randomized approach. Thereafter, no progress was made. In this work, we present a new deterministic strategy for Breaker leading to his win if q > sqrt(8/3) sqrt(n), for sufficiently large n. This almost matches the Chvátal-Erdős bound of sqrt(1/2)sqrt(n) for Maker's win (Glazik, Srivastav, Europ. J. Comb. 2022).In contrast to previous (greedy) strategies we introduce a suitable non-linear potential function on the set of nodes. By keeping the potential small, Breaker picks edges that neutralize the most ‘dangerous’ nodes with incident Maker edges blocking Maker triangles. A characteristic property of the dynamics of the game is that the total potential is not monotone decreasing. In fact, the total potential of the game may increase, even for several turns, but finally Breaker’s strategy prevents the total potential of the game from exceeding a critical level, which results in Breaker’s win. We further survey recent results for cycles of length k, and a general potential function theorem (Sowa, Srivastav 2023). This is joint work with Christian Glazik, Christian Schielke and Mathias Sowa, Kiel University.

Dante Luber Technische Universität Berlin

Initial degenerations of Grassmannian via matroid subdivisions of hypersimplices

Abstract.

Nonempty initial degenerations of the Grassmannian are induced by weight functions in its tropicalization. On the other hand, the same weight function induces a regular matroidal subdivision of the hypersimplex. Hence, we study initial degenerations of the (3,8) Grassmannian via matroidal subdivisions of the (3,8) hypersimplex. Our techniques employ tropical, algebraic, and polyhedral geometry, as well as matroid theory, commutative algebra, and computation.

Tibor Szabó Freie Universität Berlin

Topology at the North Pole

Abstract.

In the max-min allocation problem a set P of players are to be allocated disjoint subsets of a set R of indivisible resources, such that the minimum utility among all players is maximized. We study the restricted variant, also known as the Santa Claus problem, where each resource has an intrinsic positive value, and each player covets a subset of the resources. Bezakova and Dani showed that this problem is NP-hard to approximate within a factor less than 2, consequently a great deal of work has focused on approximate solutions. The principal approach for obtaining approximation algorithms has been via the Configuration LP (CLP) of Bansal and Sviridenko. Accordingly, there has been much interest in bounding the integrality gap of this CLP. The existing algorithms and integrality gap estimations are all based one way or another on the combinatorial augmenting tree argument of Haxell for finding perfect matchings in certain hypergraphs. Here we introduce the use of topological tools for the restricted max-min allocation problem. This approach yields substantial improvements in the integrality gap of the CLP. In particular we improve the previously best known bound of 3.808 to 3.534. The talk represents joint work with Penny Haxell.

Wolfgang Mulzer Freie Universität Berlin

The Multiplicative-Weights-Update Method

Abstract.

The multiplicative weights update method is a design paradigm for algorithms that is used in many different areas of theoretical computer science and machine learning.A famous survey by Arora, Hazan, and Kale provides an excellent overview over the method and its applications. Together with Nabil Mustafa, we are currently working on a monograph that explores the method in more detail. I will give an overview of the method and share some nuggets that we encountered. Based on joint work with Nabil Mustafa.

Günter Rote Freie Universität Berlin

Grid Peeling and the Affine Curve-Shortening Flow

Abstract.

Grid Peeling is the process of taking the integer grid points inside a convex region and repeatedly removing the convex hull vertices. On the other hand, the Affine Curve-Shortening Flow (ACSF) is defined as a particular deformation of a smooth curve. It has been observed in 2017 by Eppstein, Har-Peled, and Nivasch, that, as the grid is refined, Grid Peeling converges to the Affine Curve-Shortening Flow. As part of the M.Ed. thesis of Moritz Rüber, we have investigated the grid peeling process for special parabolas, and we could observe some striking phenomena. This has lead to the precise value of the constant that relates the two processes. With Morteza Saghafian from IST Austria, we could prove the convergence of grid peeling for the class of parabolas with vertical axis.

Günter Rote Freie Universität Berlin

The Generalized Combinatorial Lasoń-Alon-Zippel-Schwartz Nullstellensatz Lemma

Abstract.

We survey strengthenings and generalizations of the Schwartz-Zippel Lemma and Alon’s Combinatorial Nullstellensatz. Both lemmas guarantee the existence of (a certain number of) nonzeros of a multivariate polynomial when the variables run independently through sufficiently large ranges.

Herman Haverkort Universität Bonn

Space-filling curves: properties, applications and challenges

Abstract.

A space-filling curve is a continuous, surjective map from [0,1] to a d-dimensional unit volume (for example, a cube or a simplex). Space-filling curves are usually constructed following a recursive tessellation of the unit volume that gives the curve useful structural properties. The most prominent of these properties is that the curve tends to preserve locality: points that are close to each other along the curve are (usually) close to each other in d-dimensional space and (usually) vice versa. This can be exploited to speed up algorithms, in practice and sometimes even in theory, by processing or storing data points in order along the curve. In this lecture I will show how space-filling curves can be described, how they get their useful properties, and I will show examples of their applications. This brings us to the question what would be the optimal space-filling curves for these applications. We will encounter a number of open questions on tessellations in 2D and 3D and on how to measure the quality of a space-filling curve.

Bill Zwicker Union College, USA

Higher-order Condorcet cycles

Abstract.

In an ordinary Condorcet cycle one can identify, for each candidate, a second candidate preferred, by a majority of voters, to the first. In a Condorcet cycle of order 2 one can identify, for each pair of candidates, a third candidate preferred, by a majority of voters, to both. We construct two Condorcet cycles of order 2. The first, with 11 alternatives and 11 voters, improves the example of 15 alternatives and 15 voters given in [1]. The second, with 7 alternatives and 21 voters, shows that the lower bound on alternatives established in [4] and [3] (and independently in [1]) is sharp. Both our constructions use the method of horizontal rotation, introduced here, which generalizes the more typical form of rotation used to construct standard Condorcet cycles. The second example also makes use of a beautifully symmetric tournament constructed in [3]. William S. Zwickera (joint work with Davide P. Cervoneb) keywords: Condorcet cycle of order 2, Condorcet winning set, tournament [1] Elkind, E., Lang, J., and Saffidine, A., Condorcet Winning Sets, Soc Choice Welf 44, 493-517 (2015) [2] Erdös, P., On a problem of graph theory, Math Gaz 47, 220-223 (1963) [3] Graham, R.L. and Spencer, J.H., A constructive solution to a tournament problem, Can Math Bul 14, 45-48 (1971) [4] Szekeres, E. and Szekeres,G., On a problem of Schütte and Erdös, Math Gaz 49, 290-293 (1965) aWilliam D Williams Professor of Mathematics Emeritus, Union College, New York; and Murat Sertel Center for Advanced Economic Studies, Istanbul Bilgi University bMathematics Department, Union College, New York

Myfanwy Evans Universität Potsdam

Enumerating triply-periodic tangles

Abstract.

Using periodic surfaces as a scaffold is a convenient route to making periodic entanglements. I will present a systematic way of enumerating new tangled periodic structures, using low-dimensional topology and combinatorics, posing the question of how to best characterise these new patterns. I will also give an insight into applications of these structures.

Wolfgang Mulzer Freie Universität Berlin

Long Alternating Paths Exist

Abstract.

Let P be a set of 2n points in convex position, such that n points are colored red and n points are colored blue. A non-crossing alternating path on P of length l is a sequence p_1, ..., p_l of l points from P so that (i) all points are pairwise distinct; (ii) any two consecutive points p_i, p_{i+1} have different colors; and (iii) any two segments p_i p_{i+1} and p_j p_{j+1} have disjoint relative interiors, for i /= j. We show that there is an absolute constant eps > 0, independent of n and of the coloring, such that P always admits a non-crossing alternating path of length at least (1 + eps)n. The result is obtained through a slightly stronger statement: there always exists a non-crossing bichromatic separated matching on at least (1 + eps)n points of P. This is a properly colored matching whose segments are pairwise disjoint and intersected by a common line. For both versions, this is the first improvement of the easily obtained lower bound of n by an additive term linear in n. The best known published upper bounds are asymptotically of order 4n/3 + o(n). Based on joint work with Pavel Valtr.

Karoly Böröczky Rényi Institute, Budapest

Facets of the Brascamp-Lieb Inequality and its Reverse form

Abstract.

The Brascamp-Lieb inequality, a generalization of Holder's inequality, is introduced, together with its reverse form generalizing the Prekopa-Leindler due to Barthe. Under certain conditions, the optimal factor in either of inequalities can be obtained using Gaussian test functions. These conditions give rise to the so-called Brascamp Lieb polytope. Algorithmic aspects of approximating the optimal factor are also discussed.

Matthias Beck San Francisco State University

Boundary h*-polynomials of rational polytopes

Abstract.

If P is a lattice polytope (i.e., P is the convex hull of finitely many integer points in R^d), Ehrhart's famous theorem asserts that the integer-point counting function |mP∩Z^d| is a polynomial in the integer variable m. Equivalently, the generating function \sum_{m \ge 0} |mP∩Z^d| t^m is a rational function of the form h*(t)/(1-t)^{d+1}; we call h*(t) the Ehrhart h*-polynomial of P. We know several necessary conditions for h*-polynomials, including results by Hibi, Stanley, and Stapledon, who used an interplay of arithmetic (integer-point structure) and topological (local h-vectors of triangulations) data of a given polytope. We introduce an alternative ansatz to understand Ehrhart theory through the h*-polynomial of the boundary of a polytope, recovering all of the above results and their extensions for rational polytopes in a unifying manner. This is joint work with Esme Bajo (UC Berkeley).

János Pach Alfréd Rényi Mathematical Institute of the Hungarian Academy of Science, Budapest

Facets of Simplicity

Abstract.

We discuss some notoriously hard combinatorial problems for large classes of graphs and hypergraphs arising in geometric, algebraic, and practical applications. These structures are of bounded complexity: they can be embedded in a bounded-dimensional space, or have small VC-dimension, or a short algebraic description. What are the advantages of low complexity? I will suggest a few possible answers to this question, and illustrate them with classical examples.

Katharina Jochemko KTH Stockholm

The Eulerian transformation

Abstract.

Many polynomials arising in combinatorics are known or conjectured to have only real roots. One approach to these questions is to study transformations that preserve the real-rootedness property. This talk is centered around the Eulerian transformation which is the linear transformation that sends the i-th standard monomial to the i-th Eulerian polynomial. Eulerian polynomials appear in various guises in enumerative and geometric combinatorics and have many favorable properties, in particular, they are real-rooted and symmetric. We discuss how these properties carry over to the Eulerian transformation. In particular, we disprove a conjecture by Brenti (1989) concerning the preservation of real roots, extend recent results on binomial Eulerian polynomials and provide enumerative and geometric interpretations. This is joint work with Petter Brändén.

Torsten Ueckerdt Karlsruher Institut für Technologie, KIT

Stack and Queue Layouts of Planar Graphs

Abstract.

A colored linear layout of a graph is a total ordering of its vertices together with a partition of its edges into color classes. In a stack layout each color class is crossing-free, in a queue layout each color class is nesting-free, while in both cases our goal is to minimize the number of colors. In this talk we discuss on a higher level approaches to find good stack or queue layouts for planar graphs, including some recent breakthroughs and open problems.

Andrew Newman Carnegie Mellon University, Pittsburgh

Complexes of nearly maximum diameter

Abstract.

The combinatorial diameter of a simplicial complex is the diameter of its dual graph. Using a probabilistic approach we determine the right first-order asymptotics for the maximum possible diameter among all d-complexes on n vertices as well as among all d-pseudomanifolds on n vertices. This is joint work with Tom Bohman.

Tomáš Masarik Charles University Prague

Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument

Abstract.

We revisit recent developments for the Maximum Weight Independent Set problem in graphs excluding a subdivided claw St,t,t as an induced subgraph [Chudnovsky, Pilipczuk, Pilipczuk, Thomassé, SODA 2020] and provide a subexponential-time algorithm with improved running time 2O(n√logn) and a quasipolynomial-time approximation scheme with improved running time 2O(ε−1log5n). The Gyárfás' path argument, a powerful tool that is the main building block for many algorithms in Pt-free graphs, ensures that given an n-vertex Pt-free graph, in polynomial time we can find a set P of at most t−1 vertices, such that every connected component of G−N[P] has at most n/2 vertices. Our main technical contribution is an analog of this result for St,t,t-free graphs: given an n-vertex St,t,t-free graph, in polynomial time we can find a set P of O(tlogn) vertices and an extended strip decomposition (an appropriate analog of the decomposition into connected components) of G−N[P] such that every particle (an appropriate analog of a connected component to recurse on) of the said extended strip decomposition has at most n/2 vertices. In the talk, we first show how Gyárfás' path argument works on Pt-free graphs. Then we will sketch-prove our main result with as few technical details as possible. Joint work with: Konrad Majewski, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, Marek Sokołowski

Carlos Amendola Technische Universität München

Estimating Gaussian mixtures using sparse polynomial moment systems

Abstract.

The method of moments is a statistical technique for density estimation that solves a system of moment equations to estimate the parameters of an unknown distribution. A fundamental question critical to understanding identifiability asks how many moment equations are needed to get finitely many solutions and how many solutions there are. Since the moments of a mixture of Gaussians are polynomial expressions in the means, variances and mixture weights, one can address this question from the perspective of algebraic geometry. With the help of tools from polyhedral geometry, we answer this fundamental question for several classes of Gaussian mixture models. Furthermore, these results allow us to present an algorithm that performs parameter recovery and density estimation, applicable even in the high dimensional case. Based on joint work with Julia Lindberg and Jose Rodriguez (University of Wisconsin-Madison).

Neil Olver London School of Economics and Political Science

Continuity, Uniqueness and Long-Term Behaviour of Nash Flows Over Time

Abstract.

We consider a dynamic model of traffic that has received a lot of attention in the past few years. Users control infinitesimal flow particles aiming to travel from a source to destination as quickly as possible. Flow patterns vary over time, and congestion effects are modelled via queues, which form whenever the inflow into a link exceeds its capacity. We answer some rather basic questions about equilibria in this model: in particular uniqueness (in an appropriate sense), and continuity: small perturbations to the instance or to the traffic situation at some moment cannot lead to wildly different equilibrium evolutions. To prove these results, we make a surprising connection to another question: whether, assuming constant inflow into the network at the source, do equilibria always eventually settle into a "steady state" where all queue delays change linearly forever more? Cominetti et al. proved this under an assumption that the inflow rate is not larger than the capacity of the network - eventually, queues remain constant forever. We resolve the more general question positively. (Joint work with Leon Sering and Laura Vargas Koch).

George Mertzios Durham University, UK

Algorithmic Problems on Temporal Graphs

Abstract.

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 G1, G2, ... 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. This lecture has been recorded.

Günter Rote Freie Universität Berlin

The maximum number of minimal dominating sets in a tree

Abstract.

A tree with n vertices has at most 95n/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.

María A. Hernández Cifre Universidad de Murcia

On discrete Brunn-Minkowski type inequalities

Abstract.

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.

Vera Traub ETH Zürich

Better-Than-2 Approximations for Weighted Tree Augmentation

Abstract.

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.

Florin Manea Universität Göttingen

Combinatorial String Solving

Abstract.

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.

Arnaud Casteigts Université de Bordeaux

Spanners and connectivity problems in temporal graphs

Abstract.

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.

Henry Adams Institute of Science and Technology Austria

Open questions on clique complexes of graphs

Abstract.

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.

Markus Brill Technische Universität Berlin

Approval-Based Apportionment

Abstract.

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.

Tim Netzer Uni Innsbruck

Free Semialgebraic Geometry and Quantum Information Theory

Abstract.

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.

Manfred Scheucher Technische Universität Berlin

Erdős-Szekeres-type Problems on Planar Point Sets

Abstract.

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

Florian Frick Carnegie Mellon University and FU Berlin

Topological methods in graph theory

Abstract.

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.

Penny Haxell University of Waterloo

Tashkinov trees

Abstract.

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

Frédéric Havet INRIA Sophia-Antipolis

Unavoidability and universality of digraphs

Abstract.

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 nF such that F is nF-unavoidable (resp. nF-universal) if and only if F is acyclic, (resp. an oriented forest). However, determining the smallest nF 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.

Papa Sissokho Illinois State University

Geometry of the minimal solutions of a linear Diophantine Equation

Abstract.

Let a1,...,an and b1,...,bm be fixed positive integers, and let S denote the set of all nonnegative integer solutions of the equation x1a1+...+xnan=y1b1+...+ymbm. A solution (x1,...,xn,y1,...,ym) 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 xi = bj and yj = ai 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.

Xavier Allamigeon Inria and Ecole Polytechnique

Formalizing the theory of polyhedra in a proof assistant

Abstract.

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.

Alexey Pokrovskiy University College London

Linear size Ramsey numbers of hypergraphs

Abstract.

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.

Alex Postnikov MIT

Polypositroids

Abstract.

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.

Michael Joswig Technische Universität Berlin

Tropical bisectors and Voronoi diagrams

Abstract.

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.

Max Klimm Technische Universität Berlin

Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games

Abstract.

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)

Chris Eur Stanford University

Tautological classes of matroids

Abstract.

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.

Kolja Knauer Universitat de Barcelona

On sensitivity in Cayley graphs

Abstract.

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.

Peter Bürgisser Technische Universität Berlin

Optimization, Complexity and Invariant Theory

Abstract.

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

Helena Bergold Fern Universität Hagen

Topological Drawings meet Classical Theorems of Convex Geometry

Abstract.

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.

Michaela Borzechowski

One-Permutation-Discrete-Contraction is UEOPL-hard

Abstract.

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.

Florian Frick Carnegie Mellon University

New applications of the Borsuk--Ulam theorem

Abstract.

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.

Sampada Kolhatkar affiliation not specified

Bivariate chromatic polynomials of mixed graphs

Abstract.

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–Pö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.

Matthias Himmelmann

Generalized Principal Component Analysis for Algebraic Varieties

Abstract.

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.

Hussein Houdrouge

Subquadratic High-Dimensional Hierarchical Clustering

Stefan Mengel CNRS

A Biased Introduction to Decomposable Negation Normal Forms

Abstract.

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.

Lisa Sauermann Institute for Advanced Study, Princeton

On the extension complexity of low-dimensional polytopes

Abstract.

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.

Markus Bläser Universität Saarbrücken

Irreversibility of tensors of minimal border rank and barriers for fast matrix multiplication

Abstract.

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.

Sophie Spirkl University of Waterloo

k-coloring graphs with forbidden induced subgraphs

Abstract.

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.

Mikkel Abrahamsen University of Copenhagen

A framework for ∃R-completeness of two-dimensional packing problems

Abstract.

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.

Amitabh Basu Johns Hopkins University Baltimore

Complexity of cutting plane and branch-and-bound algorithms

Abstract.

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.

Mikkel Abrahamsen University of Copenhagen

Geometric Multicut: Shortest Fences for Separating Groups of Objects in the Plane

Abstract.

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.

Alina Stancu Concordia University Montréal

Examples and usage of discrete curvature in convex geometry problems

Abstract.

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.

Lionel Pournin Université Paris 13

Recent results on the diameter of lattice polytopes

Abstract.

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.

Haim Kaplan Tel Aviv University

Privately Learning Thresholds

Abstract.

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.

Holger Dell IT University of Copenhagen

Counting and sampling small subgraphs

Abstract.

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.

Eric Fusy École Polytechnique Paris

Bijections between families of walks using oriented planar maps

Abstract.

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 2n are in bijection with walks of length 2n ending at 0, both being counted by the central binomial coefficient). I will show examples of such relations for 2d walks where the equi-enumeration can be bijectively explained using planar maps endowed with certain orientations (Schnyder woods, bipolar orientations).

Frank Sottile Texas University

Irrational toric varieties and the secondary polytope

Abstract.

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.

Paweł Dłotko Swansea University

Topology in Action

Abstract.

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.

Svante Linusson Königlich Technische Hochschule Stockholm

Limit shape of shifted staircase SYT

Abstract.

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

Georg Loho London School of Economics and Political Science

Signed tropical convexity

Abstract.

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.

Matthias Reitzner Universität Osnabrück

Stars of Empty Simplices

Abstract.

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.

Tibor Szabó Freie Universität Berlin

Turán numbers, projective norm graphs, quasirandomness

Abstract.

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.

Günter Rote Freie Universität Berlin

Lattice paths with states, and counting geometric objects via production matrices

Abstract.

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

Alexandre Vigny Universität Bremen

Query enumeration and nowhere dense classes of graphs

Abstract.

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?

Otfried Cheong Universität Bayreuth

Convex Covers and Translation Covers

Abstract.

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.

Vijay Vazirani University of California, Irvine

Matching is as Easy as the Decision Problem, in the NC Model

Abstract.

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

Anita Liebenau University of New South Wales, Sydney

Enumerating graphs and other discrete structures by degree sequence

Abstract.

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.

Rekha R. Thomas University of Washington

Graph Density Inequalities and Sums of Squares

Abstract.

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.

Emo Welzl ETH Zürich

Connectivity of Triangulation Flip Graphs in the Plane

Abstract.

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.

Matthias Beck San Francisco State University

Lonely Runner Polyhedra

Abstract.

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.

William T. Trotter Georgia Institute of Technology

Stability Analysis for Posets

Abstract.

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.

Matthew Kahle Ohio State University

Configuration spaces of hard disks in an infinite strip

Abstract.

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.

Boaz Slomka Weizmann Institute of Science, Rehovot Israel

On Hadwiger's covering conjecture

Abstract.

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

Matthias Köppe University of California

Facets of cut-generating functionology

Abstract.

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.

Kolja Knauer Aix-Marseille Université

Tope graphs of (Complexes of) Oriented Matroids

Abstract.

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.

Kaie Kubjas Sorbonne Université Paris

Nonnegative rank four boundaries

Abstract.

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.

Sergio Cabello Universität Ljubljana

Computational geometry, optimization and Shapley values

Abstract.

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.

Karim Adiprasito Hebrew University of Jerusalem

Triangulated manifolds, Lefschetz conjectures and the revenge of marriages

Abstract.

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

Peter Gritzmann Technische Universität München

On dynamic discrete tomography: Constrained flow and multi assignment problems for plasma particle tracking

Abstract.

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)

Maria Bras Amorós Universitat Rovira i Virgili Tarragona

On numerical semigroups

Abstract.

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.

Penny Haxell University of Waterloo

Algorithms for independent transversals vs. small dominating sets

Abstract.

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.

Péter Pál Pach Budapest University of Technology and Economics

The polynomial method and the cap set problem

Abstract.

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.

Shagnik Das Freie Universität Berlin

Randomly perturbed Ramsey problems

Abstract.

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

Marijn Heule University of Texas, Austin

Everything's Bigger in Texas: "The Largest Math Proof Ever"

Abstract.

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.

László Kozma Freie Universität Berlin

Self-adjusting data structures: trees and heaps

Abstract.

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.

Marcin Pilipczuk University of Warsaw

The square root phenomenon: subexponential algorithms in sparse graph classes

Abstract.

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.

Jörg Rambau Universität Bayreuth

Optimal Diplomacy

Abstract.

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.

Christoph Berkholz Humboldt-Universität zu Berlin

A comparison of algebraic and semi-algebraic proof systems

Abstract.

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/

Henning Meyerhenke Humboldt-Universität zu Berlin

Algorithms for Large-scale Network Analysis

Abstract.

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.

Alexander Fink Queen Mary University London

Stiefel tropical linear spaces

Abstract.

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.

Facets of Complexity Monday Lectures 📅