Past Combinatorial Theory Seminar

Let $p_c$ and $q_c$ be the threshold and the expectation threshold, respectively, of an increasing family $F$ of subsets of a finite set $X$. Recently, Park and Pham proved Kahn–Kalai conjecture stating that a not-too-large multiple of $q_c$ is an upper bound on $p_c$. In the talk, I will present a slight improvement to the Park–Pham theorem, which is obtained from transferring the threshold result from the small $p$ regime to general $p$. Based on joint work with Oliver Riordan.

"Colouring" a tournament means partitioning its vertex set into acylic subsets; and the "domination number" is the size of the smallest set of vertices with no common in-neighbour. In some ways these are like the corresponding concepts for graphs, but in some ways they are very different. We give a survey of some recent results and open questions on these topics.

Joint with Tung Nguyen and Alex Scott.

We determine the minimal forbidden minors characterising the class of countable graphs that embed into some compact surface. We will also discuss Thomas’s conjecture that the Robertson—Seymour Graph Minor Theorem extends to countably infinite graphs. [https://arxiv.org/abs/2301.11042]

A classic result of Chvatál and Erdős (1972) asserts that, if the vertex-connectivity of a graph G is at least as large as its independence number, then G has a Hamilton cycle. We prove a similar result, implying that a graph G is pancyclic, namely it contains cycles of all lengths between 3 and |G|: we show that if |G| is large and the vertex-connectivity of G is larger than its independence number, then G is pancyclic. This confirms a conjecture of Jackson and Ordaz (1990) for large graphs.

I will discuss statistical inference problems on edge-correlated stochastic block models. We determine the information-theoretic threshold for exact recovery of the latent vertex correspondence between two correlated block models, a task known as graph matching. As an application, we show how one can exactly recover the latent communities using multiple correlated graphs in parameter regimes where it is information-theoretically impossible to do so using just a single graph. Furthermore, we obtain the precise threshold for exact community recovery using multiple correlated graphs, which captures the interplay between the community recovery and graph matching tasks. This is based on joint work with Julia Gaudio and Anirudh Sridhar.

In 1977, Erdős and Hajnal made the conjecture that, for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ has a clique or stable set of size at least $|G|^c$; and they proved that this is true with $|G|^c$ replaced by $2^{c\sqrt{\log |G|}}$. Until now, there has been no improvement on this result (for general $H$). We recently proved a strengthening: that for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ with $|G|\ge 2$ has a clique or stable set of size at least $2^{c\sqrt{\log |G| \log\log|G|}}$. This talk will outline the proof. Joint work with Matija Bucić, Tung Nguyen and Alex Scott.

Random greedy algorithms became ubiquitous in Combinatorics after Rödl's nibble (semi-random method), which was repeatedly refined for various applications, such as iterative graph colouring algorithms (Molloy-Reed) and lower bounds for the Ramsey number $R(3,t)$ via the triangle-free process (Bohman-Keevash / Fiz Pontiveros-Griffiths-Morris). More recently, when combined with absorption, they have played a key role in many existence and approximate counting results for combinatorial structures, following a paradigm established by my proofs of the Existence of Designs and Wilson's Conjecture on the number of Steiner Triple Systems. Here absorption (converting approximate solutions to exact solutions) is generally the most challenging task, which has spurred the development of many new ideas, including my Randomised Algebraic Construction method, the Kühn-Osthus Iterative Absorption method and Montgomery's Addition Structures (for attacking the Ryser-Brualdi-Stein Conjecture). The design and analysis of a suitable guiding mechanism for the random process can also come with major challenges, such as in the recent proof of Erdős' Conjecture on Steiner Triple Systems of high girth (Kwan-Sah-Sawhney-Simkin). This talk will survey some of this background and also mention some recent results on the Queens Problem (Bowtell-Keevash / Luria-Simkin / Simkin) and the Existence of Subspace Designs (Keevash-Sah-Sawhney). I may also mention recent solutions of the Talagrand / Kahn-Kalai Threshold Conjectures (Frankston-Kahn-Narayanan-Park / Park-Pham) and thresholds for Steiner Triple Systems / Latin Squares (Keevash / Jain-Pham), where the key to my proof is constructing a suitable spread measure via a guided random process.

A regular bipartite tournament is an orientation of a complete balanced bipartite graph $K_{2n,2n}$ where every vertex has its in- and outdegree both equal to $n$. In 1981, Jackson conjectured that any regular bipartite tournament can be decomposed into Hamilton cycles. We prove this conjecture for sufficiently large $n$. Along the way, we also prove several further results, including a conjecture of Liebenau and Pehova on Hamilton decompositions of dense bipartite digraphs.

Let $p \ge 3$ be a prime integer. The density of a non-empty solution set of a system of affine equations $L_i(x) = b_i$, $i=1,\dots,k$ on a vector space over the field $\mathbb{F}_p$ is determined by the dimension of the linear subspace $\langle L_1,\dots,L_k \rangle$, and tends to $0$ with the dimension of that subspace. In particular, if the solution set is dense, then the system of equations contains at most boundedly many pairwise distinct linear forms. In the more general setting of systems of affine conditions $L_i(x) \in E_i$ for some strict subsets $E_i$ of $\mathbb{F}_p$ and where the solution set and its density are taken inside $S^n$ for some non-empty subset $S$ of $\mathbb{F}_p$ (such as $\{0,1\}$), we can however usually find subsets of $S^n$ with density at least $1/2$ but such that the linear subspace $\langle L_1,\dots,L_k \rangle$ has arbitrarily high dimension. We shall nonetheless establish an approximate boundedness result: if the solution set of a system of affine conditions is dense, then it contains the solution set of a system of boundedly many affine conditions and which has approximately the same density as the original solution set. Using a recent generalisation by Gowers and the speaker of a result of Green and Tao on the equidistribution of high-rank polynomials on finite prime fields we shall furthermore prove a weaker analogous result for polynomials of small degree.

Based on joint work with Timothy Gowers (College de France and University of Cambridge).

I will discuss the difficult problem of proving reasonable bounds in the multidimensional generalization of Szemerédi's theorem and describe a proof of such bounds for sets lacking nontrivial configurations of the form (x,y), (x,y+z), (x,y+2z), (x+z,y) in the finite field model setting.

In this talk, I will review some recent progress on random graph matching problems, that is, to recover the vertex correspondence between a pair of correlated random graphs from the observation of two unlabelled graphs. In this talk, I will touch issues of information threshold, efficient algorithms as well as complexity theory. This is based on joint works with Hang Du, Shuyang Gong and Zhangsong Li.

We present two ways of obtaining hypercontractive inequalities for low-degree functions on compact Lie groups: one based on Ricci curvature bounds, the Bakry-Emery criterion and the representation theory of compact Lie groups, and another based on a (very different) probabilistic coupling approach. As applications we make progress on a question of Gowers concerning product-free subsets of the special unitary groups, and we also obtain 'mixing' inequalities for the special unitary groups, the special orthogonal groups, the spin groups and the compact symplectic groups. We expect that the latter inequalities will have applications in physics.

Based on joint work with Guy Kindler (HUJI), Noam Lifshitz (HUJI) and Dor Minzer (MIT).

The triangle removal lemma of Ruzsa and Szemerédi is a fundamental result in extremal graph theory; very roughly speaking, it says that if a graph is "far" from triangle-free, then it contains "many" triangles. Despite decades of research, there is still a lot that we don't understand about this simple statement; for example, our understanding of the quantitative dependencies is very poor.

In this talk, I will discuss asymmetric versions of the triangle removal lemma, where in some cases we can get almost optimal quantitative bounds. The proofs use a mix of ideas coming from graph theory, number theory, probabilistic combinatorics, and Ramsey theory.

Based on joint work with Lior Gishboliner and Asaf Shapira.

We consider a bond percolation on the hypercube in the supercritical regime. We derive vertex-expansion properties of the giant component. As a consequence we obtain upper bounds on the diameter of the giant component and the mixing time of the lazy random walk on the giant component. This talk is based on joint work with Joshua Erde and Michael Krivelevich.

We prove that every finite colouring of the plane contains a monochromatic pair of points at an odd (integral) distance from each other. We will also discuss some further results with Rose McCarty and Michal Pilipczuk concerning prime and polynomial distances.

Tom Hutchcroft and I have been working to develop a general theory of percolation on arbitrary finite transitive graphs. This extends from percolation on local approximations to infinite graphs, such as a sequence of tori, to percolation on the complete graphs - the Erdős-Rényi model. I will summarise our progress on the basic questions: When is there a phase transition for the emergence of a giant cluster? When is the giant cluster unique? How does this relate to percolation on infinite graphs? I will then sketch our proof that for finite transitive graphs with uniformly bounded vertex degrees, the supercritical giant cluster is unique, verifying a conjecture of Benjamini from 2001.

In 1973, Erdős conjectured the existence of high girth $(n,3,2)$-Steiner systems. Recently, Glock, Kühn, Lo, and Osthus and independently Bohman and Warnke proved the approximate version of Erdős' conjecture. Just this year, Kwan, Sah, Sawhney, and Simkin proved Erdős' conjecture. As for Steiner systems with more general parameters, Glock, Kühn, Lo, and Osthus conjectured the existence of high girth $(n,q,r)$-Steiner systems. We prove the approximate version of their conjecture. This result follows from our general main results which concern finding perfect or almost perfect matchings in a hypergraph $G$ avoiding a given set of submatchings (which we view as a hypergraph $H$ where $V(H)=E(G)$). Our first main result is a common generalization of the classical theorems of Pippenger (for finding an almost perfect matching) and Ajtai, Komlós, Pintz, Spencer, and Szemerédi (for finding an independent set in girth five hypergraphs). More generally, we prove this for coloring and even list coloring, and also generalize this further to when $H$ is a hypergraph with small codegrees (for which high girth designs is a specific instance). A number of applications in various areas follow from our main results including: Latin squares, high dimensional permutations, and rainbow matchings. This is joint work with Luke Postle.

A graph has a pair $(m,f)$ if it has an induced subgraph on $m$ vertices and $f$ edges. We write $(n,e)\rightarrow (m,f)$  if any graph on $n$ vertices and $e$ edges has a pair $(m,f)$.  Let  $$S(n,m,f)=\{e: ~(n,e)\rightarrow (m,f)\} ~{\rm and}$$     $$\sigma(m,f) =   \limsup_{n\rightarrow \infty}\frac{ |S(n,m,f)|}{\binom{n}{2}}.$$ These notions were first introduced and investigated by Erdős, Füredi, Rothschild, and Sós. They found five pairs $(m,f)$ with  $\sigma(m,f)=1$ and showed that for all other pairs $\sigma(m,f)\leq 2/3$.  We extend these results in two directions.

First, in a joint work with Weber, we show that not only $\sigma(m,f)$ can be zero, but also $S(n,m,f)$  could be empty for some pairs $(m,f)$ and any sufficiently large $n$. We call such pairs $(m,f)$ absolutely avoidable.

Second, we consider a natural analogue $\sigma_r(m,f)$ of $\sigma(m,f)$ in the setting of $r$-uniform hypergraphs.  Weber showed that for any $r\geq 3$ and  $m>r$,  $\sigma_r(m,f)=0$ for most values of $f$.  Surprisingly, it was not immediately clear whether there are nontrivial pairs $(m,f)$,  $(f\neq 0$, $f\neq \binom{m}{r}$,  $r\geq 3$),  for which $\sigma_r(m,f)>0$. In a joint work with Balogh, Clemen, and Weber we show that $\sigma_3(6,10)>0$ and conjecture that in the $3$-uniform case $(6,10)$ is the only such pair.

A Latin square of order n is an n by n grid filled with n different symbols so that every symbol occurs exactly once in each row and each column, while a transversal in a Latin square is a collection of cells which share no row, column or symbol. The Ryser-Brualdi-Stein conjecture states that every Latin square of order n should have a transversal with n-1 elements, and one with n elements if n is odd. In 2020, Keevash, Pokrovskiy, Sudakov and Yepremyan improved the long-standing best known bounds on this conjecture by showing that a transversal with n-O(log n/loglog n) elements exists in any Latin square of order n. In this talk, I will discuss how to show, for large n, that a transversal with n-1 elements always exists.

A random $d$-regular graph is just a $d$-regular simple graph on $[n]=\{1,2,\ldots,n\}$ chosen uniformly at random from all such graphs. This model, with $d=d(n)$, is one of the most natural random graph models, but is quite tricky to work with/reason about, since actually generating such a graph is not so easy. For $d$ constant, Bollobás's configuration model works well; for larger $d$ one can combine this with switching arguments pioneered by McKay and Wormald. I will discuss recent progress with Nick Wormald, pushing linear-time generation up to $d=o(\sqrt{n})$. One ingredient is reciprocal rejection sampling, a trick for 'accepting' a certain graph with a probability proportional to $1/N(G)$, where $N(G)$ is the number of certain configurations in $G$. The trick allows us to do this without calculating $N(G)$, which would take too long.

From each point of a Poisson point process start growing a balloon at rate 1. When two balloons touch, they pop and disappear. Will balloons reach the origin infinitely often or not? We answer this question for various underlying spaces. En route we find a new(ish) 0-1 law, and generalize bounds on independent sets that are factors of IID on trees. Joint work with Omer Angel and Gourab Ray.

In 1983 Thomassen conjectured that every graph of sufficiently large average degree has a subgraph of large girth and large average degree. While this conjecture remains open, recent evidence suggests that something stronger might be true; perhaps the subgraph can be made induced when a clique and biclique are forbidden. We overview our proof for removing 4-cycles from $K_{t,t}$-free bipartite graphs. Moreover, we discuss consequences to tau-boundedness, which is an analog of chi-boundedness.

A 1-independent bond percolation model on a graph $G$ is a probability distribution on the spanning subgraphs of $G$ in which, for all vertex-disjoint sets of edges $S_1$ and $S_2$, the states (i.e. present or not present) of the edges in $S_1$ are independent of the states of the edges in $S_2$. Such models typically arise in renormalisation arguments applied to independent percolation models, or percolation models with finite range dependencies. A 1-independent model is said to percolate if the random subgraph has an infinite component with positive probability. In 2012 Balister and Bollobás defined $p_{\textrm{max}}(G)$ to be the supremum of those $p$ for which there exists a 1-independent bond percolation model on $G$ in which each edge is present in the random subgraph with probability at least $p$ but which does not percolate. A fundamental and challenging problem in this area is to determine, or give good bounds on, the value of $p_{\textrm{max}}(G)$ when $G$ is the lattice graph $\mathbb{Z}^2$. Since $p_{\textrm{max}}(\mathbb{Z}^n)\leq p_{\textrm{max}}(\mathbb{Z}^{n-1})$, it is also of interest to establish the value of $\lim_{n\to\infty}p_{\textrm{max}}(\mathbb{Z}^n)$.

In this talk we will present a significantly improved upper bound for this limit as well as improved upper and lower bounds for $p_{\textrm{max}}(\mathbb{Z}^2)$. We will also show that with high confidence we have $p_{\textrm{max}}(\mathbb{Z}^n)<p_{\textrm{max}}(\mathbb{Z}^2)$ for large $n$ and discuss some open problems concerning 1-independent models on other graphs.

This is joint work with Tom Johnston and Alex Scott.

In this talk we explore structural results about sets with small doubling in k dimensions. We start in the continuous world with a sharp stability result for the Brunn-Minkowski inequality conjectured by Figalli and Jerison and work our way to the discrete world, where we discuss the natural extension: we show that non-degenerate sets in Z^k with doubling close to 2^k are close to convex progressions i.e. convex sets intersected with a sub-lattice. This talk is based on joint work with Peter van Hintum and Hunter Spink.

In this talk we discuss solution of the well-known problem of Erdős and Sauer from 1975 which asks for the maximum number of edges an $n$-vertex graph can have without containing a $k$-regular subgraph, for some fixed integer $k\geq 3$. We prove that any $n$-vertex graph with average degree at least $C_k\log\log n$ contains a $k$-regular subgraph. This matches the lower bound of Pyber, Rödl and Szemerédi and substantially
improves an old result of Pyber, who showed that average degree at least $C_k\log n$ is enough.

Our method can also be used to settle asymptotically a problem raised by Erdős and Simonovits in 1970 on almost regular subgraphs of sparse graphs and to make progress on the well-known question of Thomassen from 1983 on finding subgraphs with large girth and large average degree.

Joint work with Oliver Janzer