2021/08/12 by Rajko Nenadov, Nenadov, Rajko
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2108.05687
openalex publication_date 2021/08/12 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
Estimating the probability that the Erdős-Rényi random graph G(n,m) is H-free, for a fixed graph H, is one of the fundamental problems in random graph theory. If m is such that each edge of G(n,m) belongs to a copy of H' for every H' ⊆ H, in expectation, then it is known that G(n,m) is H-free with probability exp(- Θ(m)). The KLR conjecture, slightly rephrased, states that if we further condition on uniform edge distribution, the archetypal property of random graphs, the probability of being H-free becomes superexponentially small in the number of edges. While being interesting on its own, the conjecture has received significant attention due to its connection with the sparse regularity lemma, and the many results in random graphs that follow. It was proven by Balogh, Morris, and Samotij and, independently, by Saxton and Thomason, as one of the first applications of the hypergraph containers method. We give a new direct proof using induction.