Small subsets inherit sparse -regularity

DOI10.1016/J.JCTB.2006.03.004MaRDI QIDQ858679zbMATH OpenOpenAlexWikidataFDO

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

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)

Recommendations

• Regular pairs in sparse random graphs I
• Szemerédi's regularity Lemma for matrices and sparse graphs
• A characterization for sparse -regular pairs
• Holes in graphs
• A sparse regular approximation lemma

Cites work

• scientific article; zbMATH DE number 3675949 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 1080356 (Why is no real title available?)
• scientific article; zbMATH DE number 1944144 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 2086426 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• A probabilistic counting Lemma for complete graphs
• An extremal problem for random graphs and the number of graphs with large even-girth
• Arithmetic progressions of length three in subsets of a random set
• K₅‐free subgraphs of random graphs
• Large triangle-free subgraphs in graphs without \(K_ 4\)
• On \(K^ 4\)-free subgraphs of random graphs
• On graphs with small subgraphs of large chromatic number
• On triangle-free random graphs
• On universality of graphs with uniformly distributed edges
• Random Ramsey graphs for the four-cycle
• Regular pairs in sparse random graphs I
• Szemerédi’s Regularity Lemma for Sparse Graphs
• The Turn Theorem for Random Graphs
• The sparse regularity lemma and its applications
• Turán's extremal problem in random graphs: Forbidding even cycles
• Turán's extremal problem in random graphs: Forbidding odd cycles
• Turán's theorem in sparse random graphs
• \(K_4\)-free subgraphs of random graphs revisited

Cited in

(31)

• Holes in graphs
• The size Ramsey number of short subdivisions of bounded degree graphs
• A spanning bandwidth theorem in random graphs
• The size‐Ramsey number of cubic graphs
• Sparse multipartite graphs as partition universal for graphs with bounded degree
• On the KŁR conjecture in random graphs
• Local resilience for squares of almost spanning cycles in sparse random graphs
• On the size-Ramsey number of grid graphs
• Perfect matchings in \(\varepsilon\)-regular graphs and the blow-up lemma
• Threshold behavior of multi-path random key pre-distribution for sparse wireless sensor networks
• Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
• On the number of orientations of random graphs with no directed cycles of a given length
• Independent sets in hypergraphs
• The size‐Ramsey number of short subdivisions
• On the Minimum Degree of Minimal Ramsey Graphs for Cliques Versus Cycles
• \(K_4\)-free subgraphs of random graphs revisited
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• A note on counting orientations
• A characterization for sparse \(\varepsilon\)-regular pairs
• Extremal results in sparse pseudorandom graphs
• Regular pairs in sparse random graphs I
• Sparse partition universal graphs for graphs of bounded degree
• On the size-Ramsey number of grids
• Tilings in graphons
• Combinatorial theorems in sparse random sets
• Small \(\dot{B}^{-1}_{\infty,\infty}\) implies regularity
• Asymmetric Ramsey properties of random graphs involving cliques
• Covering cycles in sparse graphs
• Regularity inheritance in pseudorandom graphs
• A new proof of the KŁR conjecture
• Random directed graphs are robustly Hamiltonian

This page was built for publication: Small subsets inherit sparse \(\varepsilon\)-regularity

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