On the KŁR conjecture in random graphs

DOI10.1007/s11856-014-1120-1zbMath1303.05175arXiv1305.2516OpenAlexW2097225291WikidataQ101500307 ScholiaQ101500307MaRDI QIDQ476516

Wojciech Samotij, David Conlon, Timothy Gowers, Mathias Schacht

Publication date: 2 December 2014

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

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

zbMATH Keywords

sparse graphsequipartitions

Mathematics Subject Classification ID

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

Related Items

Dirac-type theorems in random hypergraphs, Large Rainbow Cliques in Randomly Perturbed Dense Graphs, Triangle-free subgraphs of random graphs, A new proof of the KŁR conjecture, Combinatorial theorems in sparse random sets, Triangle resilience of the square of a Hamilton cycle in random graphs, The threshold bias of the clique-factor game, Local resilience for squares of almost spanning cycles in sparse random graphs, Diagonal Ramsey via effective quasirandomness, 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, Largest subgraph from a hereditary property in a random graph, SYMMETRIC AND ASYMMETRIC RAMSEY PROPERTIES IN RANDOM HYPERGRAPHS, Extremal results in sparse pseudorandom graphs, Almost all Steiner triple systems are almost resolvable, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Hypergraph containers, Triangle-Free Subgraphs of Random Graphs, Client-waiter games on complete and random graphs, An analytic approach to sparse hypergraphs: hypergraph removal, Ramsey Goodness of Clique Versus Paths in Random Graphs, Minimum rainbow \(H\)-decompositions of graphs, The typical structure of sparse $K_{r+1}$-free graphs, Ramsey games near the critical threshold, On Komlós’ tiling theorem in random graphs, A sharp threshold for van der Waerden's theorem in random subsets, Small rainbow cliques in randomly perturbed dense graphs, Towards the Kohayakawa–Kreuter conjecture on asymmetric Ramsey properties, An asymmetric random Rado theorem: 1-statement, Independent sets in hypergraphs, Orientation Ramsey Thresholds for Cycles and Cliques, The regularity method for graphs with few 4‐cycles, A relative Szemerédi theorem

Cites Work

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