Weak expansion and strong regularity

Abstract: In previous work, embedding large graphs into subgraphs of random graphs is generally done vertex by vertex, using the Sparse Regularity Lemma, looking only one step ahead, and maintaining regularity properties throughout using a technical tool called inheritance of regularity. This approach cannot work for very sparse random graphs, even though it is believed that the embedding statements do remain true. We develop an alternative approach, showing that given a partial embedding and looking several steps ahead, the set of extensions has a weak expansion property; leveraging this one can perform vertex by vertex embedding without the need for inheritance of regularity, and as a result the approach works in sparser random graphs. In order to make this approach work, we need to use a strengthened version of the Sparse Regularity Lemma.

I will outline the new approach briefly, and explain how to use it to prove two new results.

(i) For any $\gamma>0$ and integers $r$, $D$ and $\Delta$, there is $c>0$ such that if $p\ge n^{-1/D+\gamma}$ then $\Gamma=G(n,p)$ with high probability has the following property. However $\Gamma$ is $r$-coloured, there is a colour class which contains all $cn$-vertex graphs with degeneracy at most $D$ and maximum degree at most $\Delta$.

(ii) If $p\ge n^{-1+o(1)}$, then the random $k$-uniform hypergraph $\Gamma=G^{(k)}(n,p)$ with high probability has the following property. Every subgraph $G$ of $\Gamma$ with minimum codegree at least $(\frac12+o(1))pn$ contains a tight Hamilton cycle.

Both these results are asymptotically optimal. This is joint work with Julia Böttcher and with Olaf Parczyk and Vincent Pfenninger.

combinatoricsprobability

Audience: researchers in the topic

---

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).

---