On the KŁR conjecture in random graphs

DOI10.1007/S11856-014-1120-1zbMATH Open1303.05175arXiv1305.2516OpenAlexW2097225291WikidataQ101500307 ScholiaQ101500307MaRDI QIDQ476516FDOQ476516

Authors: David Conlon, Wojciech Samotij, W. Timothy Gowers, M. Schacht 

Publication date: 2 December 2014

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Abstract: The K{L}R conjecture of Kohayakawa, {L}uczak, and R"odl 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"odl. 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.

Full work available at URL: https://arxiv.org/abs/1305.2516

Recommendations

• A new proof of the KŁR conjecture
• On \(K^ 4\)-free subgraphs of random graphs
• Towards the 0-statement of the Kohayakawa-Kreuter conjecture
• Combinatorial theorems in sparse random sets
• The Blow-up Lemma

zbMATH Keywords

sparse graphsequipartitions

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Density (toughness, etc.) (05C42) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Tiling Turán theorems
• \(H\)-factors in dense graphs
• The minimum degree threshold for perfect graph packings
• Hypergraph regularity and the multidimensional Szemerédi theorem
• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• Embedding large subgraphs into dense graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Regularity Lemma for k-uniform hypergraphs
• Flag algebras
• The counting lemma for regular k‐uniform hypergraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the maximal number of independent circuits in a graph
• On the structure of linear graphs
• Proof of the Alon-Yuster conjecture
• On the connection between chromatic number, maximal clique and minimal degree of a graph
• Triangle-free four-chromatic graphs
• Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Some Theorems on Abstract Graphs
• Extremal results in sparse pseudorandom graphs
• Extremal results for random discrete structures
• Combinatorial theorems in sparse random sets
• On sets of integers containing k elements in arithmetic progression
• Hypergraph containers
• Independent sets in hypergraphs
• Weak hypergraph regularity and linear hypergraphs
• The primes contain arbitrarily long arithmetic progressions
• The number of cliques in graphs of given order and size
• Weak quasi-randomness for uniform hypergraphs
• Dirac's theorem for random graphs
• Arithmetic progressions of length three in subsets of a random set
• On Certain Sets of Integers
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• Clique polynomials have a unique root of smallest modulus
• Lower bounds on the number of triangles in a graph
• Bandwidth theorem for random graphs
• On Sets of Acquaintances and Strangers at any Party
• Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
• A variant of the hypergraph removal lemma
• On \(K^ 4\)-free subgraphs of random graphs
• Corrádi and Hajnal's theorem for sparse random graphs
• Regularity lemmas for graphs
• Szemerédi’s Regularity Lemma for Sparse Graphs
• Threshold Functions for Ramsey Properties
• A probabilistic counting lemma for complete graphs
• A new proof of the graph removal lemma
• Supersaturated graphs and hypergraphs
• Graph removal lemmas
• The clique density theorem
• On the Minimal Density of Triangles in Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Upper tails for subgraph counts in random graphs
• \(K_4\)-free subgraphs of random graphs revisited
• Ramsey properties of random discrete structures
• Decompositions, approximate structure, transference, and the Hahn-Banach theorem
• K₅‐free subgraphs of random graphs
• The Turn Theorem for Random Graphs
• Stability results for random discrete structures
• Randomness and regularity
• Small subsets inherit sparse \(\varepsilon\)-regularity
• Title not available (Why is that?)
• On triangle-free random graphs
• Dense \(H\)-free graphs are almost \((\chi (H)-1)\)-partite
• Szemerédi's regularity Lemma for matrices and sparse graphs
• The sparse regularity lemma and its applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the number of complete subgraphs and circuits contained in graphs
• The Algorithmic Aspects of the Regularity Lemma
• Title not available (Why is that?)
• On a theorem of Rademacher-Turán
• ODD Cycles of Specified Length in Non-Bipartite Graphs
• The chromatic thresholds of graphs
• Regular pairs in sparse random graphs I
• Sur les relations symétriques dans l'ensemble fini
• An approximate version of Sidorenko's conjecture
• \(H\)-free graphs of large minimum degree

Cited In (37)

• The size‐Ramsey number of cubic graphs
• On an anti-Ramsey threshold for random graphs
• On the number of orientations of random graphs with no directed cycles of a given length
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Dirac-type theorems in random hypergraphs
• Independent sets in hypergraphs
• Combinatorial theorems in sparse random sets
• Hypergraph containers
• Minimum rainbow \(H\)-decompositions of graphs
• Ramsey games near the critical threshold
• Probabilistic hypergraph containers
• A sharp threshold for van der Waerden's theorem in random subsets
• Transference for loose Hamilton cycles in random 3-uniform hypergraphs
• Local resilience for squares of almost spanning cycles in sparse random graphs
• On Komlós' tiling theorem in random graphs
• A new proof of the KŁR conjecture
• Triangle-free subgraphs of random graphs
• The typical structure of sparse \(K_{r+1}\)-free graphs
• A relative Szemerédi theorem
• The threshold bias of the clique-factor game
• Triangle resilience of the square of a Hamilton cycle in random graphs
• Extremal results in sparse pseudorandom graphs
• Directed graphs with lower orientation Ramsey thresholds
• Almost all Steiner triple systems are almost resolvable
• An analytic approach to sparse hypergraphs: hypergraph removal
• Small rainbow cliques in randomly perturbed dense graphs
• Towards the Kohayakawa-Kreuter conjecture on asymmetric Ramsey properties
• Large Rainbow Cliques in Randomly Perturbed Dense Graphs
• Client-waiter games on complete and random graphs
• Largest subgraph from a hereditary property in a random graph
• Orientation Ramsey thresholds for cycles and cliques
• Triangle-free subgraphs of random graphs
• An asymmetric random Rado theorem: 1-statement
• Ramsey goodness of clique versus paths in random graphs
• Diagonal Ramsey via effective quasirandomness
• The regularity method for graphs with few 4‐cycles
• Symmetric and asymmetric Ramsey properties in random hypergraphs

This page was built for publication: On the KŁR conjecture in random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476516)