The University College London (UCL) Combinatorics Seminar is held every Monday at 4–5pm during term time.

The venue for seminars this term is Room 346 at the SSEES Bulding, 14–16 Taviton Street.

To subscribe to the mailing list, please email Luke Collins on luke [dot] collins [dot] 22 [at] ucl [dot] ac [dot] uk.

Next Speaker

• 27th October 2025 - Natalie Behague (University of Warwick)

  On random regular graphs and the Kim-Vu Sandwich Conjecture

  
  

  The random regular graph $G_d(n)$ is selected uniformly at random from all $d$-regular graphs on $n$ vertices. This model is a lot harder to study than the Erdős-Renyi binomial random graph model $G(n, p)$ as the probabilities of edges being present are not independent. However, in the regime $d \gg \log n$, various graph properties including Hamiltonicity and chromatic number were shown (with hard work) to be the same in $G_d(n)$ as in $G(n, p)$ with $np = d$, which inspired Kim and Vu to conjecture that when $d \gg \log n$ it is possible to ‘sandwich’ the random regular graph $G_d(n)$ between two Erdős-Renyi random graphs with similar edge density. A proof of this sandwich conjecture would unify all the previous separate hard-won results. 

  Various authors have proved weaker versions of the sandwich conjecture with incrementally improved bounds on d — the previous state of the art was due to Gao, Isaev and McKay who proved the conjecture for $d \gg (\log n)^4$. I will sketch our new proof of the full conjecture.

  This is joint work with Richard Montgomery and Daniel Il’kovič.