An approximate blow-up lemma for sparse pseudorandom graphs

Peter Allen, Julia Böttcher, Hiệp Hàn, Yoshiharu Kohayakawa, Yury Person

Type: Article

Publication Date: 2013-11-01

Citations: 0

DOI: https://doi.org/10.1016/j.endm.2013.10.061

View Publication

Locations

Electronic Notes in Discrete Mathematics - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	A counting lemma for sparse pseudorandom hypergraphs	2015	Yoshiharu Kohayakawa Guilherme Oliveira Mota Mathias Schacht Anusch Taraz
+	Embedding graphs with bounded degree in sparse pseudorandom graphs	2004	Yoshiharu Kohayakawa V. Rödl Papa A. Sissokho
+	Impossibility and Optimality Results on Constructing Pseudorandom Permutations	2007	Yuliang Zheng Tsutomu Matsumoto Hideki Imai
+	The Exact Complexity of Pseudorandom Functions and Tight Barriers to Lower Bound Proofs.	2021	Zhiyuan Fan Jiatu Li Tianqi Yang
+	Counting results for sparse pseudorandom hypergraphs I	2017	Yoshiharu Kohayakawa Guilherme Oliveira Mota Mathias Schacht Anusch Taraz
+	Blow-up lemmas for sparse graphs	2016	Peter Allen Julia Böttcher Hiệp Hàn Yoshiharu Kohayakawa Yury Person
+ PDF Chat	Spectral Pseudorandomness and the Road to Improved Clique Number Bounds for Paley Graphs	2024	Dmitriy Kunisky
+	A Note on the Instance Complexity of Pseudorandom Sets.	1992	Ko K-I
+	First-order properties of bounded quantifier depth of very sparse random graphs	2017	Maksim Zhukovskii L. B. Ostrovskii
+ PDF Chat	Derandomization with Pseudorandomness	2024	Emin Karayel
+	An algorithmic version of the blow-up lemma	1998	János Komlós Gábor N. Sárközy Endre Szemerédi
+ PDF Chat	Regularity inheritance in pseudorandom graphs	2019	Peter Allen Julia Böttcher Jozef Skokan Maya Stein
+	Quasirandomness in Graphs	2006	Carola Doerr Tobias Friedrich
+	Algorithmic Aspects of Regularity	2000	Yoshiharu Kohayakawa V. Rödl
+	Random low-degree polynomials are hard to approximate	2011	Ido Ben‐Eliezer Rani Hod Shachar Lovett
+ PDF Chat	Pseudorandomness for Regular Branching Programs via Fourier Analysis	2013	Omer Reingold Thomas Steinke Salil Vadhan
+ PDF Chat	Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size	2008	V. Arvind Partha Mukhopadhyay
+	On a simple randomized algorithm for finding a 2-factor in sparse graphs	2005	Gopal Pandurangan
+	Algorithmic theory of random graphs	1997	FriezeAlan McDiarmidColin
+	Pseudorandomness	2012	Salil Vadhan

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (8)

Action	Title	Year	Authors
+	Pseudo-random Graphs	2006	Michael Krivelevich Benny Sudakov
+	Proof of the bandwidth conjecture of Bollobás and Komlós	2008	Julia Böttcher Mathias Schacht Anusch Taraz
+	Bandwidth theorem for random graphs	2011	Hao Huang Choongbum Lee Benny Sudakov
+	Blow-up Lemma	1997	János Komlós Gábor N. Sárközy Endre Szemerédi
+ PDF Chat	On the KŁR conjecture in random graphs	2014	David Conlon W. T. Gowers Wojciech Samotij Mathias Schacht
+ PDF Chat	Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs	2009	Julia Böttcher Klaas P. Pruessmann Anusch Taraz Andreas Würfl
+ PDF Chat	Ramsey-goodness—and otherwise	2013	Peter Allen Graham Brightwell Jozef Skokan
+	Extremal results in sparse pseudorandom graphs	2014	David Conlon Jacob Fox Yufei Zhao