Combinatorial Theory Seminar

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.

We consider an oriented acyclic version of the Erdős-Rényi random graph: the set of vertices is {1,...,n}, and for each pair i < j, an edge from i to j is independently added to the graph with probability p. The length of the longest path in such a graph grows linearly with the number of vertices in the graph, and its growth rate is a deterministic function C of the probability p of presence of an edge.
Foss and Konstantopoulos introduced a coupling between these graphs and a particle system called the "Infinite-bin model". By using this coupling, we prove some properties of C, that it is analytic on (0,1], its development in series at point 1 and its asymptotic behaviour as p goes to 0.

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

Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is never far from its "expectation-threshold," which is a natural (and often easy to calculate) lower bound on the threshold. In this talk, I will present recent progress on this topic. Based on joint work with Huy Tuan Pham.

We prove that with high probability $\mathbb{G}^{(3)}(n,n^{-1+o(1)})$ contains a spanning Steiner triple system for $n\equiv 1,3\pmod{6}$, establishing the exponent for the threshold probability for existence of a Steiner triple system. We also prove the analogous theorem for Latin squares. Our result follows from a novel bootstrapping scheme that utilizes iterative absorption as well as the connection between thresholds and fractional expectation-thresholds established by Frankston, Kahn, Narayanan, and Park.
This is joint work with Ashwin Sah and Michael Simkin. 

In the past few years, the study of the geometric properties of random maps has been extended to a new regime, the "high genus regime", where we are interested in maps whose size and genus tend to infinity at the same time, at the same rate.
We consider here a slightly different case, where the genus also tends to infinity, but less rapidly than the size, and we study the law of simple cycles (with a well-chosen rescaling of the graph distance) in unicellular maps (maps with one face), thanks to a powerful bijection of Chapuy, Féray and Fusy.
The interest of this work is that we obtain exactly the same law as Mirzakhani and Petri who counted closed geodesics on a model of random hyperbolic surfaces in large genus (the Weil-Petersson measure). This leads us to conjecture that these two models are somehow "the same" in the limit. This is joint work with Svante Janson.