Sprinkling with random regular graphs

2:00 pm, Wednesday, 20th March

Abstract

A technique known as sprinkling goes back to classical works of Erdős and Rényi that laid foundations of the random graph theory. This technique is also known under the name multiple-round exposure as it gradually exposes the edges of a random graph in rounds to achieve a desired graph property through additional last-minute randomisation. Sprinkling has numerous applications including studies of giant and dominant components, appearance of a Hamiltonian cycle and other important patterns, non-monotone properties related to extremal subgraphs and extension counts, the Sunflower Lemma, and the Spread Lemma, to name a few. 

In this talk, we present the recent results adopting the fruitful idea of sprinkling to the random regular graph model, which analysis is significantly more challenging in comparison to the classical models of random graphs due to intricate adjacency dependencies. We believe that sprinkling is possible in the following sense: for growing degrees, with probability tending to 1, a uniform random regular graph can be split into a union of two edge-disjoint uniform random regular graphs. We also discuss several related open questions. The talk is based on our recent preprint https://arxiv.org/pdf/2309.00190.pdf.