2013/05/11 by D. Conlon, W. T. Gowers, W. Samotij +1 · 1 citation
Mathematics · #math.CO
paper · pdf · doi:10.1007/s11856-014-1120-1
published as Israel J. Math. 203 (2014), no. 1, 535-580 · 33 pages
arxiv created 2013/05/11 · arxiv updated 2016/02/22
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 Gn,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.