Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 2014 | Submitted
Journal Article Open

On the KŁR conjecture in random graphs


The KŁR conjecture of Kohayakawa, Łuczak, and Rödl is a statement that allows one to prove that asymptotically almost surely all subgraphs of the random graph G_(n, p), for sufficiently large p := p(n), satisfy an embedding lemma which complements the sparse regularity lemma of Kohayakawa and Rödl. We prove a variant of this conjecture which is sufficient for most known applications to random graphs. In particular, our result implies a number of recent probabilistic versions, due to Conlon, Gowers, and Schacht, of classical extremal combinatorial theorems. We also discuss several further applications.

Additional Information

© Hebrew University of Jerusalem 2014. Received 11 May 2013; revised 24 January 2014; first online 21 March 2015. Conlon research supported by a Royal Society University Research Fellowship. Gowers research supported by a Royal Society 2010 Anniversary Research Professorship. Samotij research supported in part by a Trinity College JRF. Schacht research supported by the Heisenberg programme of the DFG.

Attached Files

Submitted - 1305.2516.pdf


Files (415.9 kB)
Name Size Download all
415.9 kB Preview Download

Additional details

August 22, 2023
October 18, 2023