Sparse partition universal graphs for graphs of bounded degree

DOI10.1016/j.aim.2011.01.004zbMath1227.05196OpenAlexW2078983092WikidataQ101500317 ScholiaQ101500317MaRDI QIDQ633606

Vojtěch Rödl, Endre Szemerédi, Mathias Schacht, Yoshiharu Kohayakawa

Publication date: 29 March 2011

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.aim.2011.01.004

zbMATH Keywords

random graphsuniversal graphsregularity Lemmainheritance of regularitysize-Ramsey numbers

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Generalized Ramsey theory (05C55)

Related Items

The vertex size-Ramsey number, On the size-Ramsey number of grid graphs, Rolling backwards can move you forward: On embedding problems in sparse expanders, The size‐Ramsey number of cubic graphs, Multicolor list Ramsey numbers grow exponentially, Random bipartite Ramsey numbers of long cycles, The multicolour size-Ramsey number of powers of paths, Extremal results in sparse pseudorandom graphs, Bipartite Ramsey numbers of paths for random graphs, The size Ramsey number of short subdivisions of bounded degree graphs, Sparse multipartite graphs as partition universal for graphs with bounded degree, Triangle-Free Subgraphs of Random Graphs, Lower bounds of size Ramsey number for graphs with small independence number, Almost‐spanning universality in random graphs, The tripartite Ramsey number for trees, Bipartite Ramsey numbers of cycles for random graphs, Almost spanning subgraphs of random graphs after adversarial edge removal, Size Ramsey Number of Bounded Degree Graphs for Games, The size‐Ramsey number of powers of bounded degree trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Ramsey number of a graph with bounded maximum degree
• Small subsets inherit sparse \(\varepsilon\)-regularity
• On graphs with small subgraphs of large chromatic number
• Expanding graphs contain all small trees
• An ergodic Szemerédi theorem for commuting transformations
• Spanning subgraphs of random graphs
• The size Ramsey number
• The asymptotic number of labeled graphs with given degree sequences
• Blow-up lemma
• Perfect matchings in \(\varepsilon\)-regular graphs and the blow-up lemma
• Hypergraph regularity and the multidimensional Szemerédi theorem
• On sets of integers containing k elements in arithmetic progression
• An algorithmic version of the blow-up lemma
• Szemerédi’s Regularity Lemma for Sparse Graphs
• Regular pairs in sparse random graphs I
• On size Ramsey number of paths, trees, and circuits. I
• Paths in graphs
• Regularity Lemma for k-uniform hypergraphs
• The Induced Size-Ramsey Number of Cycles
• The hypergraph regularity method and its applications
• Sparse universal graphs for bounded‐degree graphs
• The counting lemma for regular k‐uniform hypergraphs
• The size-Ramsey number of trees
• On size Ramsey numbers of graphs with bounded degree