On the KŁR conjecture in random graphs
By David Conlon, William T. Gowers, Wojciech Samotij, Mathias Schacht. Israel Journal of Mathematics, 2013
80 citations recorded by the source corpus.
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.
Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology
View Paper: https://www.semanticscholar.org/paper/da58c8edca173692ef4df76e889d9da7c476b2ac
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Discrete Mathematics and Combinatorics
In Geometry and Topology
Citations in the corpus
- Diagonal Ramsey via effective quasirandomness (2020, background): “[10, 1, 3, 19, 6, 7]) in connection with extremal graph theory and additive combinatorics.”