Sparse partition universal graphs for graphs of bounded degree

DOI10.1016/J.AIM.2011.01.004MaRDI QIDQ633606zbMATH OpenOpenAlexWikidataFDO

Authors Yoshiharu Kohayakawa, Vojtěch Rödl, M. Schacht, Endre Szemerédi

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

inheritance of regularityrandom graphsregularity Lemmasize-Ramsey numbersuniversal graphs

Mathematics Subject Classification ID

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

Recommendations

• Sparse multipartite graphs as partition universal for graphs with bounded degree
• Sparse universal graphs for bounded‐degree graphs
• Partitioning sparse graphs into an independent set and a forest of bounded degree
• Explicit sparse almost-universal graphs for G (n, kn)
• Partitioning sparse graphs into an independent set and a graph with bounded size components
• Sparse universal graphs
• scientific article; zbMATH DE number 1833411
• Sparse universal graphs for planarity
• Judicious partitions of bounded‐degree graphs
• On partitions of graphs under degree constraints

Cites work

• An algorithmic version of the blow-up lemma
• An ergodic Szemerédi theorem for commuting transformations
• Blow-up lemma
• Expanding graphs contain all small trees
• scientific article; zbMATH DE number 5764887 (Why is no real title available?)
• scientific article; zbMATH DE number 4029619 (Why is no real title available?)
• scientific article; zbMATH DE number 3724483 (Why is no real title available?)
• scientific article; zbMATH DE number 16104 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (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 1833411 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• Hypergraph regularity and the multidimensional Szemerédi theorem
• On graphs with small subgraphs of large chromatic number
• On sets of integers containing k elements in arithmetic progression
• On size Ramsey number of paths, trees, and circuits. I
• On size Ramsey numbers of graphs with bounded degree
• Paths in graphs
• Perfect matchings in \(\varepsilon\)-regular graphs and the blow-up lemma
• Regular pairs in sparse random graphs I
• Regularity Lemma for k-uniform hypergraphs
• Small subsets inherit sparse \(\varepsilon\)-regularity
• Spanning subgraphs of random graphs
• Sparse universal graphs for bounded‐degree graphs
• Szemerédi’s Regularity Lemma for Sparse Graphs
• The asymptotic number of labeled graphs with given degree sequences
• The counting lemma for regular k‐uniform hypergraphs
• The hypergraph regularity method and its applications
• The Induced Size-Ramsey Number of Cycles
• The Ramsey number of a graph with bounded maximum degree
• The size Ramsey number
• The size-Ramsey number of trees
• The sparse regularity lemma and its applications

Cited in

(27)

• Sparse universal graphs
• Bipartite Ramsey numbers of paths for random graphs
• Sparse multipartite graphs as partition universal for graphs with bounded degree
• Bipartite Ramsey numbers of cycles for random graphs
• The multicolour size-Ramsey number of powers of paths
• Lower bounds of size Ramsey number for graphs with small independence number
• Extremal results in sparse pseudorandom graphs
• The vertex size-Ramsey number
• Size Ramsey number of bounded degree graphs for games
• The size Ramsey number of short subdivisions of bounded degree graphs
• Triangle-free subgraphs of random graphs
• The size-Ramsey number of powers of bounded degree trees
• Rolling backwards can move you forward: on embedding problems in sparse expanders
• Almost-spanning universality in random graphs
• On the size-Ramsey number of grid graphs
• Constructive lower bounds for off-diagonal Ramsey numbers
• The size‐Ramsey number of cubic graphs
• Multicolor list Ramsey numbers grow exponentially
• Random bipartite Ramsey numbers of long cycles
• The size-Ramsey number of powers of bounded degree trees
• On the size-Ramsey number of grids
• Interview with David Conlon
• Size-Ramsey numbers of graphs with maximum degree three
• Effective bounds for induced size-Ramsey numbers of cycles (extended abstract)
• Partition universality for hypergraphs of bounded degeneracy and degree (extended abstract)
• Size-Ramsey numbers of structurally sparse graphs
• Embedding and Ramsey numbers of sparse \(k\)-uniform hypergraphs

This page was built for publication: Sparse partition universal graphs for graphs of bounded degree

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