The talk features a survey as well as recent new results on two independent approaches to derive efficient algorithms for integer programming, namely algorithms based on the geometry of numbers and dynamic programming techniques, with an extra spotlight on the case in which the number of constraints (apart from bounds on the variables) is small. We will highlight open problems and possible future directions. The presented results of the speaker have been jointly achieved with Daniel Dadush, Thomas Rothvoss and Robert Weismantel.

An $n$-vertex graph is called $C$-Ramsey if it has no clique or independent set of size $C log n$ (i.e., if it has near-optimal Ramsey behavior). In this talk, we discuss a result on edge-statistics in Ramsey graphs, which gives very precise control of the distribution of the number of edges in a random vertex subset of a $C$-Ramsey graph. One of the consequences of our result is the resolution of an old conjecture of Erdős and McKay. Joint work with Ashwin Sah, Lisa Sauermann and Mehtaab Sawhney.

In this talk, we are interested in minimizing $f(x) = g(Wx)$ over the set of $0/1$-vectors, where $W$ is an integral $m$ by $n$ matrix and $g$ is a convex function that is either separable convex or sharp convex. Moreover, the matrix W is unknown to us. Only the number of rows $m < n$ and $||W||$ is revealed. The composite function $f$ is presented by a zeroth and first order oracle only. Our main result is a proximity theorem that ensures that an integral minimum and a continuous minimum for separable convex and sharp convex functions are always "close" by. This will be a key ingredient to develop an algorithm for detecting an integer minimum that achieves a running time depending only polynomially on $n$, even with the restricted knowledge of the decomposition into $g$ and $W$.

This talk is based on joint work with S. Pokutta and R. Weismantel (https://arxiv.org/abs/2204.05266).

Path TSP is the generalization of the classical TSP where the start and he endpoint of the tour are prescribed and possibly distinct. We present a black-box reduction from Path TSP to the classical tour version (TSP). More precisely, we show that given an $α$-approximation algorithm for TSP, there is an $(α+ϵ)$-approximation algorithm for the more general Path TSP for any $ϵ>0$. This reduction implies that the approximability of Path TSP is the same as for TSP, up to an arbitrarily small error and avoids future discrepancies between the best known approximation factors achievable for these two problems, as they existed for several decades.

Recently, our reduction has been used by Karlin, Klein, and Oveis Gharan to derive approximation guarantees below $3/2$ for Path TSP. Moreover, our reduction also applies to Graph Path TSP, which asks for tours in unit-weight graphs. By combining it with the $1.4$-approximation algorithm for Graph TSP by Sebő and Vygen, we obtain a polynomial-time $(1.4+ϵ)$-approximation algorithm for Graph Path TSP.

This is joint work with Jens Vygen and Rico Zenklusen.

The $n$-queens problem asks how many ways there are to place n queens on an $n x n$ chessboard so that no two queens can attack one another, and the toroidal $n$-queens problem asks the same question where the board is considered on the surface of a torus. Let $Q(n)$ denote the number of n-queens configurations on the classical board and T(n) the number of toroidal n-queens configurations. The toroidal problem was first studied in 1918 by Pólya who showed that $T(n)>0$ if and only if n is not divisible by 2 or 3. Much more recently Luria showed that $T(n)$ is at most $((1+o(1))ne^{-3})^n$ and conjectured equality when n is not divisible by 2 or 3. We prove this conjecture, prior to which no non-trivial lower bounds were known to hold for all (sufficiently large) $n$ not divisible by 2 or 3. We also show that $Q(n)$ is at least $((1+o(1))ne^{-3})^n$ for all natural numbers n which was independently proved by Luria and Simkin and, combined with our toroidal result, completely settles a conjecture of Rivin, Vardi and Zimmerman regarding both $Q(n)$ and $T(n)$.

In this talk we'll discuss our methods used to prove these results. A crucial element of this is translating the problem to one of counting matchings in a 4-partite 4-uniform hypergraph. Our strategy combines a random greedy algorithm to count "almost" configurations with a complex absorbing strategy that uses ideas from the methods of randomised algebraic construction and iterative absorption.

This is joint work with Peter Keevash.

We discuss the Theorem of Izmestiev, an underappreciated result that established a strong link between the geometry of a convex polytope and the spectral properties of its edge-graph. It roughly states that the 1-skeleton of a polytope is a Colin de Verdière embedding of the edge-graph. We present two applications of this theorem that have arisen in our work:

• Conjecturally, a polytope is determined up to isometry by its edge-graph, its edge-lengths and the distance of each vertex from some point in the interior. This is a form of universal rigidity, determining the polytope across all dimensions and all combinatorial types. We show that this is true if the polytope is either centrally symmetric or of a fixed combinatorial type. This also establishes an upper bound on the dimension of the realization space of $f_0 + f_1 - d - 1$.
• edge-graphs are sufficient to capture the polytope's symmetries: one can color the edge-graph so that its symmetry group becomes isomorphic to the affine (or Euclidean) symmetry group of the polytope.

For about 40 years now, it is known that there is the same number of alternating sign matrices (ASMs) as there is of totally symmetric self-complementary plane partitions and of descending plane partitions (DPPs). Very recently, Ayyer, Behrend and myself introduced alternating sign triangles and showed that they are also counted by the same formula. Apart from a very complicated bijective proof for the equinumerosity of ASMs and DPPs by Konvalinka and myself, explicit bijective proofs of these relations are still to be found. The discovery of equivalent parameters on two classes of objects can help in this task. We will present recent work, where we have established the step from a constant number of equivalent parameters to a linear number of such parameters. This is joint work with Hans Höngesberg and Florian Schreier-Aigner.

We introduce a model of a controlled random graph process. In this model, the edges of the complete graph $K_n$ are ordered randomly and then revealed, one by one, to a player called Builder. He must decide, immediately and irrevocably, whether to purchase each observed edge. The observation time is bounded by parameter $t$, and the total budget of purchased edges is bounded by parameter $b$. Builder's goal is to devise a strategy that, with high probability, allows him to construct a graph of purchased edges possessing a target graph property $P$, all within the limitations of observationime and total budget.

We analyze this model in the context of several graph theoretic properties such as minimum degree, Hamiltonicity, and the containment of fixed-size trees and cycles.

Joint work with Alan Frieze and Peleg Michaeli.

Combinatorial game theory (CGT) is a branch of game theory formalized by Conway in "On numbers and games" (1976). In the context of CGT, thermography is a technique for analyzing the behavior of individual positions in a sufficiently rich sum of combinatorial games. Although thermographs for simple (i.e. not loopy) games are easy to compute, the case for loopy game thermography remains an open problem. The best algorithm currently known for general loopy games is due to Berlekamp (1996). However this can only solve very simple loops.

In this talk we relate the problem of computing thermographs with the well known tropical linear feasibility problem. Although it is yet unknown if tropical linear feasibility problems are in P or not, practical algorithms do exist. This would imply general game thermographs are computable. This immediately has applications for the game of Go, the most popular combinatorial game currently played.

In this talk I will present some results on variants of Hadwiger's conjecture I have obtained in the last year.

First, I will discuss the so-called Odd Hadwiger's conjecture, a strengthening of Hadwiger's conjecture proposed by Gerards and Seymour in 1995. I will show a new upper bound for coloring graphs with no odd $K_t$-minor, which improves several previous bounds for this problem and comes along with a substantially simpler proof.

Second, I will show a new bound of $2t-2$ for clustered colorings of odd $K_t$-minor free graphs, in which we look for colorings with monochromatic components of small size, this also significantly improves several previous results.

Third, I will discuss the so-called List Hadwiger's conjecture, which states that there exists a constant c such that every graph with no $K_t$-minor is $ct$-choosable (i.e., list colorable). I will present a new lower bound $2t-o(t)$ for list coloring $K_t$-minor free graphs which refutes a conjecture by Kawarabayashi and Mohar. Fourth, I will present a result saying that $K_{s,t}$-minor free graphs for large comparable $s$ and $t$ can have list chromatic number at least $(1-o(1)(s+t+min(s,t))$, this refutes a conjecture by Woodall.

Finally, I will describe a recent result obtained in joint work with Anders Martinsson that yields strengthenings of Hadwiger's conjecture for 4- and 5-chromatic graphs and confirms the first open case of a conjecture by Holroyd from 1997.

The theory of rapid mixing random walks plays a fundamental role in the study of modern randomised algorithms. Usually, the mixing time is measured with respect to the worst initial position. It is well known that the presence of bottlenecks in a graph hampers mixing and, in particular, starting inside a small bottleneck significantly slows down the diffusion of the walk in the first steps of the process. To circumvent this problem, the average mixing time is defined to be the mixing time starting at a uniformly random vertex.

In this talk we discuss a general framework to show logarithmic average mixing time for random walks on graphs with small bottlenecks. The framework is especially effective on certain families of random graphs with heterogeneous properties. We demonstrate its applicability on two random models for which the mixing time was known to be of order $\log^2n$, speeding up the mixing to order $\log n$. First, in the context of smoothed analysis on connected graphs, we show logarithmic average mixing time for randomly perturbed graphs of bounded degeneracy. A particular instance is the Newman-Watts small-world model. Second, we show logarithmic average mixing time for supercritically percolated expander graphs. When the host graph is complete, this application gives an alternative proof that the average mixing time of the giant component in the supercritical Erdős-Rényi graph is logarithmic.

Tropical geometry is the geometry over the max-plus algebra, and it is a degeneration or limit of classical geometric objects under the logarithm or valuation map. We will discuss how to tropicalize algebraic sets, semialgebraic sets, and co ex sets, and highlight an application to the truncated moment problem in real algebraic geometry.

We use tropicalization to study the cones of moments and pseudomoments, which are duals to cones of nonnegative polynomials and sums of squares on a semialgebraic set. When the semialgebraic set is defined by binomial inequalites, its moment and pseuo-moment cones are closed under Hadamard product. In this case, their tropicalizations are polyhedral cones that encode all binomial inequalities on the moment and pseudo-moment cones. We give explicit descriptions of these polyhedral cones, which can help us distinguish between moments and pseudomoments.

This is based on joint work with Grigoriy Blekherman, Felipe Rincón, Rainer Sinn, and Cynthia Vinzant

Integer Linear Programs (ILPs) are a powerful and universal tool to model various problems. However, in general, they are hard to solve. I present a block structure on the constraint matrices which makes the ILP problem solvable efficiently. Further, I give a general idea and examples on how to use these ILPs to obtain efficient algorithms for a wide range of hard problems from combinatorial optimization.

Many algorithms use data structures that maintain properties of matrices undergoing some changes. The applications are wide-ranging and include for example matchings, shortest paths, linear programming, semi-definite programming, convex hull and volume computation. Given the wide range of applications, the exact property these data structures must maintain varies from one application to another, forcing algorithm designers to invent them from scratch or modify existing ones. Thus it is not surprising that these data structures and their proofs are usually tailor-made for their specific application and that maintaining more complicated properties results in more complicated proofs. In this talk, I present a unifying framework that captures a wide range of these data structures. The simplicity of this framework allows us to give short proofs for many existing data structures regardless of how complicated the to be maintained property is. We also show how the framework can be used to speed up existing iterative algorithms, such as the simplex algorithm.

It is indisputable Ramsey-type numbers are among the most mysterious and fascinating in Combinatorics. This talk focuses on Arithmetic Ramsey numbers and Diophantine problems.I discuss methods from algebraic geometry and SAT Boolean solvers to study a family of Ramsey-type numbers arising in arithmetic Ramsey theory: The lovely Rado numbers. For a positive integer $k$ and linear equation $E$, the Rado number $R_k(E)$ is the smallest integer number $n$ such that every $k$-coloring of ${1,2,...,n}$ contains a monochromatic solution to the equation E. A very famous example are Schur numbers, which are the Rado numbers for the equation $E={x+y=z}$. (Incidentally, Issai Schur was Rado’s Ph.D advisor at Berlin in 1933). I will discuss computation, bounds, and verification of these numbers and the fascinating history of Ramsey theory, with names like Hilbert, Schur, van der Waerden, appearing along the way.

We computed many new exact values for Rado numbers of the form $R_3(ax+by+cz = 0)$ using SAT solvers. In particular, we give a method for computing infinite families of Rado numbers, solving a few open questions. Regarding complexity and verification: Suppose someone suggests to you the value of $R_k(E)$ . How can you certify that this value is correct and not a lie? We encode the problem as a system of polynomial equations and show that the degrees of Nullstellensatz certificates are actually bounded above by another Ramsey-number arising in a two-player game. The extremal k-colorings are in fact the solutions of this system which says that proving that the proposed value of $R_k(E)$ is not correct may require a doubly exponential certificate. At the heart is how combinatorial algebraic geometry relates to Ramsey numbers. This is joint work with Ph.D candidate Jack Wesley.