Small subsets inherit sparse \(\varepsilon\)-regularity

DOI10.1016/j.jctb.2006.03.004zbMath1111.05090OpenAlexW2030380672WikidataQ105583648 ScholiaQ105583648MaRDI QIDQ858679

Angelika Steger, Vojtěch Rödl, Stefanie Gerke, Yoshiharu Kohayakawa

Publication date: 11 January 2007

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2006.03.004

zbMATH Keywords

quasi-randomness\(C_{\ell}\)-free graphsmall witness to high chromatic numbersparse regularity lemma

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Related Items

On the Minimum Degree of Minimal Ramsey Graphs for Cliques Versus Cycles ⋮ On the size-Ramsey number of grid graphs ⋮ A spanning bandwidth theorem in random graphs ⋮ A new proof of the KŁR conjecture ⋮ Combinatorial theorems in sparse random sets ⋮ Local resilience for squares of almost spanning cycles in sparse random graphs ⋮ The size‐Ramsey number of cubic graphs ⋮ The size‐Ramsey number of short subdivisions ⋮ Covering cycles in sparse graphs ⋮ On the number of orientations of random graphs with no directed cycles of a given length ⋮ Bounded-Degree Spanning Trees in Randomly Perturbed Graphs ⋮ Sparse partition universal graphs for graphs of bounded degree ⋮ Extremal results in sparse pseudorandom graphs ⋮ Threshold behavior of multi-path random key pre-distribution for sparse wireless sensor networks ⋮ On the KŁR conjecture in random graphs ⋮ Tilings in graphons ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ The size Ramsey number of short subdivisions of bounded degree graphs ⋮ \(K_4\)-free subgraphs of random graphs revisited ⋮ Sparse multipartite graphs as partition universal for graphs with bounded degree ⋮ Asymmetric Ramsey properties of random graphs involving cliques ⋮ Random directed graphs are robustly Hamiltonian ⋮ Almost spanning subgraphs of random graphs after adversarial edge removal ⋮ A note on counting orientations ⋮ Independent sets in hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On graphs with small subgraphs of large chromatic number
• Large triangle-free subgraphs in graphs without \(K_ 4\)
• On universality of graphs with uniformly distributed edges
• An extremal problem for random graphs and the number of graphs with large even-girth
• Random Ramsey graphs for the four-cycle
• On \(K^ 4\)-free subgraphs of random graphs
• Turán's extremal problem in random graphs: Forbidding even cycles
• Turán's extremal problem in random graphs: Forbidding odd cycles
• \(K_4\)-free subgraphs of random graphs revisited
• Szemerédi’s Regularity Lemma for Sparse Graphs
• Regular pairs in sparse random graphs I
• Turán's theorem in sparse random graphs
• K₅‐free subgraphs of random graphs
• On triangle-free random graphs
• The Turn Theorem for Random Graphs
• Arithmetic progressions of length three in subsets of a random set