Past Combinatorial Theory Seminar

I will describe some recent work with D. Kazhdan where we obtain results in algebraic geometry, inspired by questions in additive combinatorics, via analysis over finite fields. Specifically we are interested in quantitative properties of polynomial rings that are independent of the number of variables. A sample application is the following theorem : Let $V$ be a complex vector space, $P$ a high rank polynomial of degree $d$, and $X$ the null set of $P$, $X=\{v \mid P(v)=0\}$. Any function $f:X\to C$ which is polynomial of degree $d$ on lines in $X$ is the restriction of a degree $d$ polynomial on $V$.

The classical Erdős-Szekeres theorem dating back almost a hundred years states that any sequence of $(n-1)^2+1$ distinct real numbers contains a monotone subsequence of length $n$. This theorem has been generalised to higher dimensions in a variety of ways but perhaps the most natural one was proposed by Fishburn and Graham more than 25 years ago. They raise the problem of how large should a $d$-dimesional array be in order to guarantee a "monotone" subarray of size $n \times n \times \ldots \times n$. In this talk we discuss this problem and show how to improve their original Ackerman-type bounds to at most a triple exponential. (Joint work with M. Bucic and T. Tran)

A Latin square of order n is an $n \times n$ array filled with $n$ symbols such that each symbol appears only once in every row or column and a transversal is a collection of cells which do not share the same row, column or symbol. The study of Latin squares goes back more than 200 years to the work of Euler. One of the most famous open problems in this area is a conjecture of Ryser, Brualdi and Stein from 60s which says that every Latin square of order $n \times n$ contains a transversal of order $n-1$. A closely related problem is 40 year old conjecture of Brouwer that every Steiner triple system of order $n$ contains a matching of size $\frac{n-4}{3}$. The third problem we'd like to mention asks how many distinct symbols in Latin arrays suffice to guarantee a full transversal? In this talk we discuss a novel approach to attack these problems. Joint work with Peter Keevash, Alexey Pokrovskiy and Benny Sudakov.

I will discuss the percolation model on planar triangulations, and present a bijection that is key to relating this model to some fundamental probabilistic objects. I will attempt to achieve several goals:
1. Present the site-percolation model on random planar triangulations.
2. Provide an informal introduction to several probabilistic objects: the Gaussian free field, Schramm-Loewner evolutions, and the Brownian map.
3. Present a bijective encoding of percolated triangulations by certain lattice paths, and explain its role in establishing exact relations between the above-mentioned objects.
This is joint work with Nina Holden, and Xin Sun.

Random graphs with finite excess appear naturally in at least two different settings: random graphs in the critical window (aka critical percolation on regular and other classes of graphs), and unicellular maps of fixed genus. In the first situation, the scaling limit of such random graphs was obtained by Addario-Berry, Broutin and Goldschmidt based on a depth-first exploration of the graph and on the coding of the resulting forest by random walks. This idea originated in Aldous' work on the critical random graph, using instead a breadth-first search approach that seem less adapted to taking graph scaling limits. We show hat this can be done nevertheless, resulting in some new identities for quantities like the radius and the two-point function of the scaling limit. We also obtain a similar "breadth-first" construction of the scaling limit of unicellular maps of fixed genus. This is based on joint work with Sanchayan Sen.

Recent years have seen a great deal of progress in understanding the behavior of bootstrap percolation models, a particular class of monotone cellular automata. In the two dimensional lattice there is now a quite complete understanding of their evolution starting from a random initial condition, with a universality picture for their critical behavior. Here we will consider their non-monotone stochastic counterpart, namely kinetically constrained models (KCM). In KCM each vertex is resampled (independently) at rate one by tossing a $p$-coin iff it can be infected in the next step by the bootstrap model. In particular infection can also heal, hence the non-monotonicity. Besides the connection with bootstrap percolation, KCM have an interest in their own : when $p$ shrinks to 0 they display some of the most striking features of the liquid/glass transition, a major and still largely open problem in condensed matter physics.

We prove that for Bernoulli bond percolation on $\mathbb{Z}^d$, $d\geq2$, the percolation density $\theta(p)$ (defined as the probability of the origin lying in an infinite cluster) is an analytic function of the parameter in the supercritical interval $(p_c,1]$. This answers a question of Kesten from 1981.

The proof involves a little bit of elementary complex analysis (Weierstrass M-test), a few well-known results from percolation theory (Aizenman-Barsky/Menshikov theorem), but above all combinatorial ideas. We used a new notion of contours, bounds on the number of partitions of an integer, and the inclusion-exclusion principle, to obtain a refinement of a classical argument of Peierls that settled the 2-dimensional case in 2018. More recently, we coupled these techniques with a renormalisation argument to handle all dimensions.

Joint work with Christoforos Panagiotis.

Color each vertex of an infinite graph blue with probability $p$ and red with probability $1-p$, independently among vertices. For which values of $p$ is there an infinite connected component of blue vertices? The talk will focus on this classical percolation problem for the class of planar graphs. Recently, Itai Benjamini made several conjectures in this context, relating the percolation problem to the behavior of simple random walk on the graph. We will explain how partial answers to Benjamini's conjectures may be obtained using the theory of circle packings. Among the results is the fact that the critical percolation probability admits a universal lower bound for the class of recurrent plane triangulations. No previous knowledge on percolation or circle packings will be assumed.

I'll discuss our recent proof of a conjecture of Talagrand, a fractional version of the "expectation-threshold" conjecture of Kahn and Kalai. As a consequence of this result, we resolve various (heretofore) difficult problems in probabilistic combinatorics and statistical physics.

I will describe how certain recursive distributional equations can be solved by using tools from numerical analysis on the convergence of approximation schemes for PDEs. This project is joint work with Luc Devroye, Hannah Cairns, Celine Kerriou, and Rivka Maclaine Mitchell.

A covering system of the integers is a finite collection of arithmetic progressions whose union is the set of integers $\mathbb{Z}$. The study of these objects was initiated in 1950 by Erdős, and over the following decades he asked a number of beautiful questions about them. Most famously, his so-called 'minimum modulus problem' was resolved in 2015 by Hough, who proved that in every covering system with distinct moduli, the minimum modulus is at most $10^{16}$.

In this talk I will describe a simple and general method of attacking covering problems that was inspired by Hough's proof. We expect that this technique, which we call the 'distortion method', will have further applications in combinatorics.

This talk is based on joint work with Paul Balister, Béla Bollobás, Julian Sahasrabudhe and Marius Tiba.

Given a tournament with $d{n \choose 3}$ cycles of length three, how many cycles of length four must there be? Linial and Morgenstern (2016) conjectured that the minimum is asymptotically attained by "blowing up" a transitive tournament and orienting the edges randomly within the parts. This is reminiscent of the tight examples for the famous Triangle and Clique Density Theorems of Razborov, Nikiforov and Reiher. We prove the conjecture for $d \geq \frac{1}{36}$ using spectral methods. We also show that the family of tight examples is more complex than expected and fully characterise it for $d \geq \frac{1}{16}$. Joint work with Timothy Chan, Andrzej Grzesik and Daniel Král'.

Consider all planar graphs on n vertices. What is the smallest graph that contains them all as induced subgraphs? We provide an explicit construction of such a graph on $n^{4/3+o(1)}$ vertices, which improves upon the previous best upper bound of $n^{2+o(1)}$, obtained in 2007 by Gavoille and Labourel.

In this talk, we will gently introduce the audience to the notion of so-called universal graphs (graphs containing all graphs of a given family as induced subgraphs), and devote some time to a key lemma in the proof. That lemma comes from a recent breakthrough by Dujmovic et al. regarding the structure of planar graphs, and has already many interesting consequences - we hope the audience will be able to derive more. This is based on joint work with Cyril Gavoille and Michal Pilipczuk.

For a family $A$ in $\{0,...,k\}^n$, its deletion shadow is the set obtained from $A$ by deleting from any of its vectors one coordinate. Given the size of $A$, how should we choose $A$ to minimise its deletion shadow? And what happens if instead we may delete only a coordinate that is zero? We discuss these problems, and give an exact solution to the second problem.

Let us fix a prime $p$. The Erdős-Ginzburg-Ziv problem asks for the minimum integer $s$ such that any collection of $s$ points in the lattice $\mathbb{Z}^n$ contains $p$ points whose centroid is also a lattice point in $\mathbb{Z}^n$. For large $n$, this is essentially equivalent to asking for the maximum size of a subset of $\mathbb{F}_p^n$ without $p$ distinct elements summing to zero.

In this talk, we discuss a new upper bound for this problem for any fixed prime $p\geq 5$ and large $n$. Our proof uses the so-called multi-colored sum-free theorem which is a consequence of the Croot-Lev-Pach polynomial method, as well as some new combinatorial ideas.

A subset $D$ of a finite cyclic group $\mathbb{Z}/m\mathbb{Z}$ is called a "perfect difference set" if every nonzero element of $\mathbb{Z}/m\mathbb{Z}$ can be written uniquely as the difference of two elements of $D$. If such a set exists, then a simple counting argument shows that $m=n^2+n+1$ for some nonnegative integer $n$. Singer constructed examples of perfect difference sets in $\mathbb{Z}/(n^2+n+1)\mathbb{Z}$ whenever $n$ is a prime power, and it is an old conjecture that these are the only such $n$ for which $\mathbb{Z}/(n^2+n+1)\mathbb{Z}$ contains a perfect difference set. In this talk, I will discuss a proof of an asymptotic version of this conjecture.

Modularity is a function on graphs which is used in algorithms for community detection. For a given graph G, each partition of the vertices has a modularity score, with higher values indicating that the partition better captures community structure in $G$. The (max) modularity $q^\ast(G)$ of the graph $G$ is defined to be the maximum over all vertex partitions of the modularity score, and satisfies $0 \leq q^\ast(G) \leq 1$.

We analyse when community structure of an underlying graph can be determined from an observed subset of the graph. In a natural model where we suppose edges in an underlying graph $G$ appear with some probability in our observed graph $G'$ we describe how high a sampling probability we need to infer the community structure of the underlying graph.

Joint work with Colin McDiarmid.

In this talk, we consider the random version of some classical extremal problems in the context of long cycles. This type of problems can also be seen as random analogues of the Turán number of long cycles, established by Woodall in 1972.

For a graph $G$ on $n$ vertices and a graph $H$, denote by $\text{ex}(G,H)$ the maximal number of edges in an $H$-free subgraph of $G$. We consider a random graph $G\sim G(n,p)$ where $p>C/n$, and determine the asymptotic value of $\text{ex}(G,C_t)$, for every $A\log(n)< t< (1- \varepsilon)n$. The behaviour of $\text{ex}(G,C_t)$ can depend substantially on the parity of $t$. In particular, our results match the classical result of Woodall, and demonstrate the transference principle in the context of long cycles.

Using similar techniques, we also prove a robustness-type result, showing the likely existence of cycles of prescribed lengths in a random subgraph of a graph with a nearly optimal density (a nearly ''Woodall graph"). If time permits, we will present some connections to size-Ramsey numbers of long cycles.

Based on joint works with Michael Krivelevich and Adva Mond.