Title: Ramsey theory constructions from hypergraph matchings

Abstract: Erdős and Gyárfás (1997) investigated the following parameter that generalizes classical Ramsey numbers: let \(f(n,p,q)\) be the minimum number of colors required to color the edges of an \(n\)-clique so that every \(p\)-subclique receives at least \(q\) colors. This parameter has led to many interesting problems. I will show how a recent generalization of an old result of Frankl and Rödl about hypergraph matchings can be used to settle some cases of the Erdős–Gyárfás problem by giving asymptotically optimal constructions. This is joint work with Felix Joos.

Title: From triangulations to graphs and back

Abstract: I will discuss some problems in geometric topology, and relate them to graph-theoretic properties. I will give some open problems, and answer questions of Kalai, Belolipetski, Gromov and others.

Title: Random graphs and suprema of stochastic processes

Abstract: The threshold phenomenon is a central direction of study in probabilistic combinatorics, particularly the study of random graphs, and in theoretical computer science. The threshold of an increasing graph property (or more generally an increasing boolean function) is the density at which a random graph (or a random set) transitions from unlikely satisfying to likely satisfying the property (or the function). Kahn and Kalai conjectured that this threshold is always within a logarithmic factor of the expectation threshold, a natural lower bound to the threshold which is often much easier to compute. In probabilistic combinatorics and random graph theory, the Kahn–Kalai conjecture directly implies a number of difficult results, such as Shamir's problem on hypergraph matchings. I will discuss joint work with Jinyoung Park that resolves the Kahn–Kalai conjecture. I will also discuss recent joint work with Vishesh Jain that resolves a conjecture of Johansson, Keevash, and Luria and Simkin on the threshold for containment of Latin squares and Steiner triple systems, and joint work with Ashwin Sah, Mehtaab Sawhney, Michael Simkin on thresholds in robust settings. Zooming into finer details of random graphs beyond the threshold phenomenon, I will touch on nonlinear large deviation results for subgraph counts and connections to sparse regularity obtained in joint work with Nicholas Cook and Amir Dembo.

Interestingly, the proof of the Kahn–Kalai conjecture is closely related to our resolution of a conjecture of Talagrand on extreme events of suprema of certain stochastic processes driven by sparse Bernoulli random variables (known as selector processes), and a question of Talagrand on suprema of general positive empirical processes. These conjectures play an important role in generalizing the study of suprema of stochastic processes beyond the Gaussian case, and given recent advances on chaining and the resolution of the (generalized) Bernoulli conjecture, our results give the first steps towards Talagrand's last "Unfulfilled dreams" in the study of suprema of general stochastic processes.

Title: Sumset Estimates in Higher Dimensions

Abstract: We will describe recent progress, in joint work with Jeck Lim, on the study of sumset estimates in higher dimensions. The basic question we discuss is the following: given a subset \(A\) of \(d\)-dimensional space and a linear transformation \(L\), how large is the sumset \(A + LA\)?

Title: The Integrality Gap for the Santa Claus Problem

Abstract: In the max-min allocation problem, a set of players are to be allocated disjoint subsets of a set of indivisible resources, such that the minimum utility among all players is maximized. In the restricted variant, also known as the Santa Claus Problem, each resource ("toy") has an intrinsic positive value, and each player ("child") covets a subset of the resources. Thus Santa wants to distribute the toys amongst the children, while (to satisfy jealous parents?) wishing to maximize the minimum total value of toys received by each child. This problem turns out to have a natural reformulation in terms of hypergraph matching.

Bezakova and Dani showed that the Santa Claus problem is NP-hard to approximate within a factor less than 2, consequently a great deal of work has focused on approximate solutions. To date, the principal approach for obtaining approximation algorithms has been via the Configuration LP of Bansal and Sviridenko, and bounds on its integrality gap. The existing algorithms and integrality gap estimations tend to be based one way or another on a combinatorial local search argument for finding perfect matchings in certain hypergraphs.

Here we introduce a different approach, which in particular replaces the local search technique with the use of topological methods for finding hypergraph matchings. This yields substantial improvements in the integrality gap of the CLP, from the previously best known bound of 3.808 for the general problem to 3.534. We also address the well-studied special case in which resources can take only two values, and improve the integrality gap in most cases. This is based on joint work with Tibor Szabo.

Title: Friendly Bisections of Random Graphs

Abstract: It is easy to partition the vertices of any graph into two sets where each vertex has at least as many neighbours across as on its own side; take any maximal cut! Can we do the opposite? This is not possible in general, but Füredi conjectured in 1988 that it should nevertheless be possible on a random graph. I shall talk about our recent proof of Füredi's conjecture: with high probability, the random graph \(G(n,1/2)\) on an even number of vertices admits a partition of its vertex set into two parts of equal size in which \(n - o(n)\) vertices have more neighbours on their own side than across.