Combinatorial Theory Seminar

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

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.

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.

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.