On the KLR conjecture in sparse random graphs

Other Talks
Friday, October 5, 2012 - 4:00pm
1 hour (actually 50 minutes)
**Emory University**, Mathematics and Science Center, Rm W201
Math, University of Hamburg, Germany
(**This is at Emory and is a joint Emory - Georgia Tech Combinatorics Seminar. **)  The KLR conjecture of Kohayakawa, Luczak, and Rödl is a statement that allows one to prove that asymptotically almost surely all subgraphs of the random graph G(n,p) 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 applications to random graphs. In particular, our result implies a number of recent probabilistic threshold results. We also discuss several further applications. This joint work with Conlon, Gowers, and Samotij.