Combinatorial Theory Seminar

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.

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.

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.

Dobrushin (1972) showed that, at low enough temperatures, the interface of the 3D Ising model - the random surface separating the plus and minus phases above and below the $xy$-plane - is localized: it has $O(1)$ height fluctuations above a fixed point, and its maximum height $M_n$ on a box of side length $n$ is $O_P(\log n)$. We study this interface and derive a shape theorem for its "pillars" conditionally on reaching an atypically large height. We use this to analyze the maximum height $M_n$ of the interface, and prove that at low temperature $M_n/\log n$ converges to $c\beta$ in probability. Furthermore, the sequence $(M_n - E[M_n])_{n\geq 1}$ is tight, and even though this sequence does not converge, its subsequential limits satisfy uniform Gumbel tails bounds.
Joint work with Reza Gheissari.

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.

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.

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