Extremal and Probabilistic Combinatorics

It is natural to expect that nonbacktracking random walk will mix faster than simple random walks, but so far this has only been proved in regular graphs. To analyze typical irregular graphs, let $G$ be a random graph on $n$ vertices with minimum degree 3 and a degree distribution that has exponential tails. We determine the precise mixing time for simple random walk on $G$ from all starting points: with high probability, this mixing time is asymptotically $\mathbf{h}^{-1} \log n$, where $\mathbf{h}$ is the asymptotic entropy for simple random walk on a Galton--Watson tree that approximates $G$ locally. (Previously this was only known for typical starting points.) Furthermore, we show that this asymptotic mixing time is strictly larger than the mixing time of nonbacktracking walk, via a delicate comparison of entropies on the Galton--Watson tree. Joint work with A. Ben-Hamou and Y. Peres

In a celebrated paper from 1995, Kim proved $R(3,t) \ge c t^2/\log t$ by constructing a triangle-free n-vertex graph with independence number at most $C \sqrt{n \log n}$. We extend this result, by approximately decomposing the complete graph $K_n$ into edge-disjoint copies of such `nearly Ramsey optimal' graphs. More precisely, for any $\epsilon>0$ we find a collection $(G_i)_i$ of edge-disjoint triangle-free graphs $G_i \subseteq K_n$ such that (a) each $G_i$ has independence number at most $C_\epsilon \sqrt{n \log n}$, and (b) the union of the $G_i$ contains at least $(1-\epsilon)\binom{n}{2}$ edges. As an application we prove a conjecture of Fox, Grinsh, Liebenau, Person, and Szabo in Ramsey theory (concerning r-Ramsey-minimal graphs for $K_3$). Based on joint work with He Guo.

Models arising from the action of monotone (two-state) cellular automata on random subsets of $\mathbb{Z}^d$ or $\mathbb{Z}_n^d$ are known as bootstrap percolation. In this talk I will describe a new universality theory for bootstrap percolation, which is motivated by the following vague question: to what extent does the global behaviour of the models depend on the local details of the model itself? That is, to what extent is the global behaviour of the models universal? To grossly oversimplify, the answer is that every monotone cellular automaton behaves `roughly' like an $r$-neighbour model, for some $r \in \{1,2,\dots,d+1\}$, where these are defined according to the rule that new sites become active at time $t+1$ if at least $r$ of their $2d$ nearest neighbours are active at time $t$.

A graph G is called \emph{universal} with respect to a family of graph F, if it contains all members of F as (not nec. induced) subgraphs. In this talk we are interested in finding $p$ as small as possible for which $G(n,p)$ is F-universal where F is the family of all graphs on n vertices with max degree $D$. Currently, the best known $p$ is due to Dellamonica, Kohayakawa, R\"odl and Ruci\'nski and is $p = \Omega(n^{-1/\Delta}\log^c)$. The conjectured bound is $n^{-2/(D+1)}\log^c$ which is much smaller. Even though a better bound is known for the almost spanning case (due to Conlon, Ferber, Nenadov and Skoric), the spanning case seems much harder. In this talk we survey this problem and show that $n^{-1/(D-1/2)}\log^c$ is enough for all $D\geq 3$ and that the conjectured $p$ is correct for $D=2$. Based on a joint work with Rajko Nenadov, and a work with Gal Kronenberg and Kyle Luh.

For a graph $H$, the extremal or Turán number $\mathrm{ex}(n,H)$ is the maximum number of edges in a graph on $n$ vertices containing no copy of $H$. For any $H$ containing a cycle, it was conjectured by Erdős that the number $f_n(H)$ of $H$-free graphs on $n$ vertices is $2^{(1+o(1))\mathrm{ex}(n,H)}$. This has long been known to be true for graphs with chromatic number $\chi(H)\geq 3$, but does not hold in general for bipartite $H$. It is instead conjectured that $f_n(H) = 2^{O(\mathrm{ex}(n,H))}$; to date, this has been shown for relatively few examples, and often with considerable difficulty. We prove this conjecture for any bipartite $H$ that satisfies a conjecture of Erdős and Siminovits on the asymptotic behavior of $\mathrm{ex}(n,H)$. We also give an analogous result for $r$-partite $r$-uniform hypergraphs $H$. Joint work with Asaf Ferber and Wojciech Samotij.

If the positive integers are partitioned into finitely many parts $\mathbb{N} = A_1 \cup \cdots \cup A_k$ what can be said about the arithmetic structure of the parts? While it is perhaps unclear that anything can be said about such a general partition, the rich field of arithmetic Ramsey theory is devoted precisely to this question. For example, in 1916 Schur proved that if the positive integers are partitioned into finitely many parts then one of the parts must contain integers $x,y$ and their sum $x+y$. In subsequent years this field has enjoyed many advances and connections to other fields (such as ergodic theory, Fourier analysis, topology) but many difficult questions still remain.\newline In this talk I'll discuss a host of new results about exponential patterns that appear in every finite partition of the integers. These results are perhaps surprising in that these patterns are extremely ``sparse'' - in sharp contrast with known results. For example, we show that for every finite partition of the integers there exists $a,b>1$ so that the triple $\{a,b,a^b\}$ is entirely contained in a part of the partition.

A celebrated theorem of Roth from 1953 shows that every dense set of integers contains a three-term arithmetic progression. This has been the starting point for the development of an enormous amount of beautiful mathematics. In this talk, I will discuss major recent progress on the bounds on some of the well-studied extensions of Roth's theorem and related problems.

There are several conjectures trying to relate the average/minimum/median degree of a graph with it having all trees of a certain size as subgraphs. One example is the Erdos-Sos conjecture, another example is the Loebl-Komlos-Sos conjecture. We investigate a new conjecture in this direction, which says that a minimum degree of 2k/3 together with a maximum degree of k should be enough for having all trees of size k as subgraphs. The results we present are joint work with Havet, Reed and Wood, and with Reed.

The codegree threshold $\mathrm{ex}_2(n, F)$ of a non-empty $3$-uniform hypergraph $F$ is the minimum $d$ such that every $3$-uniform hypergraph on $n$ vertices in which every pair of vertices is contained in at least $d+1$ edges contains a copy of $F$ as a subgraph. In this talk, we focus on the codegree threshold of $F=K_4^-$, the $3$-uniform hypergraph on $4$ vertices with $3$ edges. Using flag algebra techniques, we prove that \[\mathrm{ex}_2(n, K_4^-)=\frac{n}{4}+O(1).\] This settles in the affirmative a conjecture of Nagle from 1999. In addition, we show that for every near-extremal configuration $G$, there is a quasirandom tournament $T$ on the same vertex-set such that $G$ is close in the so-called edit distance to the $3$-uniform hypergraph $C(T)$, whose edges are the cyclically oriented triangles from $T$. We further determine the exact value of $\mathrm{ex}_2(n, K_4^-)$ for infinitely many values of $n$ by exploiting its very close relation to the existence of skew Hadamard matrices. In fact, we show that determining the exact value of $\mathrm{ex}_2(n, K_4^-)$ for $n=4k+3$ is equivalent to Seberry's conjecture, which states that there exists a skew Hadamard matrix for every $n=4k$. Joint work with Victor Falgas-Ravry, Oleg Pighurko and Emil Vaughan.

We consider an urn model with graph based interactions and ask the question: when can two competing growths (in different colors) co-exist? We discuss this problem in finite graphs and infinite lattices. We also discuss an application to co-existence of competing bootstrap type growth models. [Based on joint work with Daniel Ahlberg, Svante Janson and Robert Morris]

I will outline an approach to embedding and counting in regular partitions of sparse hypergraphs. The talk will not assume knowledge of what the last sentence means.

Recently, Chapuy (arXiv 1603.07714) posed an intriguing conjecture regarding Voronoi cells in large random maps: for any non-negative $g$ and any $k > 1$, the masses of the $k$ nearest-neighbour Voronoi cells induced by $k$ uniform points in the genus $g$ Brownian map have the same law as a uniform $k$-division of the unit interval. \newline Motivated by this conjecture, we show that masses of Voronoi cells are distributed as uniform partitions of $[0,1]$ for a range of continuum limits of random graphs and maps, including: \newline 1. The Brownian continuum random tree (CRT)\newline 2. The Brownian unicellular map on any fixed (orientable or non-orientable) surface\newline 3. Continuum random graphs with a fixed surplus\newline Joint work in progress with Omer Angel, Guillaume Chapuy, Éric Fusy, and Christina Goldschmidt.

For a $k$-uniform hypergraph $F$ let $\textrm{ex}(n,F)$ be the maximum number of edges of a $k$-uniform $n$-vertex hypergraph $H$ which contains no copy of $F$. Determining or estimating $\textrm{ex}(n,F)$ is a classical and central problem in extremal combinatorics. While for $k=2$ this problem is well understood, due to the work of Turán and of Erdős and Stone, only very little is known for $k$-uniform hypergraphs for $k>2$. We focus on the case when $F$ is a $k$-uniform hypergraph with three edges on $k+1$ vertices. Already this very innocent (and maybe somewhat particular looking) problem is still wide open even for $k=3$. We consider a variant of the problem where the large hypergraph $H$ enjoys additional hereditary density conditions. Questions of this type were suggested by Erdős and Sós about 30 years ago. We show that every $k$-uniform hypergraph $H$ with density $>2^{1-k}$ with respect to every large collection of $k$-cliques induced by sets of $(k-2)$-tuples contains a copy of $F$. The required density $2^{1-k}$ is best possible as higher order tournament constructions show. Our result can be viewed as a common generalisation of the first extremal result in graph theory due to Mantel (when $k=2$ and the hereditary density condition reduces to a normal density condition) and a recent result of Glebov, Král', and Volec (when $k=3$ and large subsets of vertices of $H$ induce a subhypergraph of density $>1/4$). Our proof for arbitrary $k\geq 2$ utilises the regularity method for hypergraphs.

A word $w$ is said to contain the pattern $P$ if there is a way to substitute a nonempty word for each letter in $P$ so that the resulting word is a subword of $w$. Bean, Ehrenfeucht and McNulty and, independently, Zimin characterised the patterns $P$ which are unavoidable, in the sense that any sufficiently long word over a fixed alphabet contains $P$. Zimin's characterisation says that a pattern is unavoidable if and only if it is contained in a Zimin word, where the Zimin words are defined by $Z_1 = x_1$ and $Z_n=Z_{n-1} x_n Z_{n-1}$. We study the quantitative aspects of this theorem, obtaining essentially tight tower-type bounds for the function $f(n,q)$, the least integer such that any word of length $f(n, q)$ over an alphabet of size $q$ contains $Z_n$. When $n = 3$, the first non-trivial case, we determine $f(n,q)$ up to a constant factor, showing that $f(3,q) = \Theta(2^q q!)$. Joint work with Jacob Fox and Benny Sudakov.