On the KŁR conjecture in random graphs

Abstract

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.

33 pages

References in corpus (1)

• On the logarithimic calculus and Sidorenko's conjecture

Cited by in corpus (9)

• A relative Szemerédi theorem
• Combinatorial theorems relative to a random set
• Extremal results in random graphs
• Almost all Steiner triple systems are almost resolvable
• Multicolour containers and the entropy of decorated graph limits
• The regularity method for graphs with few 4-cycles
• Sharp thresholds for Ramsey properties of strictly balanced nearly bipartite graphs
• Regularity inheritance in pseudorandom graphs
• Which graphs can be counted in $C_4$-free graphs?