Sparse partition universal graphs for graphs of bounded degree

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

Type: Article

Publication Date: 2011-01-24

Citations: 54

DOI: https://doi.org/10.1016/j.aim.2011.01.004

View Publication

Locations

Advances in Mathematics - View

Similar Works

Action	Title	Year	Authors
+	The Bandwidth Theorem in Sparse Graphs	2016	Peter Allen Julia Böttcher Julia Ehrenmüller Anusch Taraz
+	The Bandwidth Theorem in Sparse Graphs	2016	Peter J. Allen Julia Böttcher Julia Ehrenmüller Anusch Taraz
+	Extremal and probabilistic results for regular graphs	2017	Ewan Davies
+	Embedding graphs with bounded degree in sparse pseudorandom graphs	2004	Yoshiharu Kohayakawa V. Rödl Papa A. Sissokho
+	Blow-up lemma for cycles in sparse random graphs	2021	Miloš Trujić
+ PDF Chat	Blow-up lemma for cycles in sparse random graphs	2021	Miloš Trujić
+ PDF Chat	Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions	2010	Noga Alon Amin Coja‐Oghlan Hiệp Hàn Mihyun Kang Vojtěch Rödl Mathias Schacht
+	Blow-up lemma for cycles in sparse random graphs	2021	Miloš Trujić
+ PDF Chat	Quasi-randomness and Algorithmic Regularity for Graphs with General Degree Distributions	2007	Noga Alon Amin Coja‐Oghlan Hiệp Hàn Mihyun Kang Vojtěch Rödl Mathias Schacht
+ PDF Chat	Canonical labelling of sparse random graphs	2024	Oleg Verbitsky Maksim Zhukovskii
+	Ramsey properties of randomly perturbed dense graphs	2019	Emil Powierski
+	Finding any given 2-factor in sparse pseudorandom graphs efficiently	2019	Jie Han Yoshiharu Kohayakawa Patrick Morris Yury Person
+	Universality of random graphs and rainbow embedding	2013	Asaf Ferber Rajko Nenadov Ueli Peter
+	The sparse regularity lemma and its applications	2005	Stefanie Gerke Angelika Steger
+	Universality of random graphs and rainbow embedding	2013	Asaf Ferber Rajko Nenadov Ueli Peter
+ PDF Chat	Factors and loose Hamilton cycles in sparse pseudo-random hypergraphs	2019	Hiệp Hàn Jie Han Patrick Morris
+	An Improved Upper Bound on the Density of Universal Random Graphs	2012	Domingos Dellamonica Yoshiharu Kohayakawa Vojtěch Rödl Andrzej Ruciński
+	Sparse Quasi-Random Graphs	2002	Fan Chung Ronald L. Graham
+	Upper Tails of Subgraph Counts in Sparse Regular Graphs	2021	Benjamin Gunby
+	Random Perfect Graphs	2016	Colin McDiarmid Nikola Yolov

Works That Cite This (53)

Action	Title	Year	Authors
+	An Approximate Blow-up Lemma for Sparse Hypergraphs	2021	Peter Allen Julia Böttcher Eng Keat Hng Jozef Skokan Ewan Davies
+ PDF Chat	The size‐Ramsey number of powers of paths	2018	Dennis Clemens Matthew Jenssen Yoshiharu Kohayakawa Natasha Morrison Guilherme Oliveira Mota Damian Reding Barnaby Roberts
+	The size Ramsey number of short subdivisions of bounded degree graphs	2018	Yoshiharu Kohayakawa Troy Retter Vojtěch Rödl
+	On the size-Ramsey number of hypergraphs	2015	Andrzej Dudek Steven La Fleur Dhruv Mubayi Vojtěch Rödl
+	Almost-spanning universality in random graphs	2015	David Conlon Asaf Ferber Rajko Nenadov Nemanja Škorić
+	The multicolour size-Ramsey number of powers of paths	2020	Jie Han Matthew Jenssen Yoshiharu Kohayakawa Guilherme Oliveira Mota Barnaby Roberts
+	Extremal results in sparse pseudorandom graphs	2014	David Conlon Jacob Fox Yufei Zhao
+ PDF Chat	Almost spanning subgraphs of random graphs after adversarial edge removal	2009	Julia Böttcher Yoshiharu Kohayakawa Anusch Taraz
+	Sparse multipartite graphs as partition universal for graphs with bounded degree	2017	Qizhong Lin Yusheng Li
+ PDF Chat	On the Size‐Ramsey Number of Hypergraphs	2017	Andrzej Dudek Steven La Fleur Dhruv Mubayi Vojtěch Rödl

Works Cited by This (35)

Action	Title	Year	Authors
+ PDF Chat	On sets of integers containing k elements in arithmetic progression	1975	Endre Szemerédi
+	Szemerédi’s Regularity Lemma for Sparse Graphs	1997	Yoshiharu Kohayakawa
+	Szemeredi''s Regularity Lemma and its applications in graph theory	1995	János Komlós Miklós Simonovits
+	The Regularity Lemma and Its Applications in Graph Theory	2002	János Komlós Ali Shokoufandeh Miklós Simonovits Endre Szemerédi
+	Regularity Lemma for k‐uniform hypergraphs	2004	Vojtěch Rödl Jozef Skokan
+	Optimal universal graphs with deterministic embedding	2008	Noga Alon Michael Capalbo
+	Regular pairs in sparse random graphs I	2003	Yoshiharu Kohayakawa V. Rödl
+	Surveys in Combinatorics 2005	2005	B. S Webb
+	The asymptotic number of labeled graphs with given degree sequences	1978	Edward A. Bender E. Rodney Canfield
+	Spanning subgraphs of random graphs	1992	Noga Alon Zoltán Füredi