A short proof of Gowers’ lower bound for the regularity lemma

Guy Moshkovitz, A. Shapira

Type: Article

Publication Date: 2014-11-05

Citations: 24

DOI: https://doi.org/10.1007/s00493-014-3166-4

View Publication

Download PDF

Locations

arXiv (Cornell University) - View - PDF
CiteSeer X (The Pennsylvania State University) - View - PDF
COMBINATORICA - View

Similar Works

Action	Title	Year	Authors
+	A Short Proof of Gowers' Lower Bound for the Regularity Lemma	2013	Guy Moshkovitz A. Shapira
+	A Short Proof of Gowers' Lower Bound for the Regularity Lemma	2013	Guy Moshkovitz A. Shapira
+	A tight lower bound for Szemerédi's regularity lemma	2014	Jacob Fox László Lovász
+	A tight lower bound for Szemerédi's regularity lemma	2014	Jacob Fox László Lovász
+	A tight lower bound for Szemer\'edi's regularity lemma	2014	Jacob Fox László Lovász
+	A Tight Bound for Hypergraph Regularity II	2018	Guy Moshkovitz A. Shapira
+ PDF Chat	An improved lower bound for arithmetic regularity	2016	Kaave Hosseini Shachar Lovett Guy Moshkovitz A. Shapira
+ PDF Chat	A Tight Bound for Hyperaph Regularity	2019	Guy Moshkovitz A. Shapira
+	Bounds for graph regularity and removal lemmas	2011	David Conlon Jacob Fox
+	Bounds for graph regularity and removal lemmas	2011	David Conlon Jacob Fox
+	Szémeredi's regularity lemma and its applications in combinatorics	2006	Jonas Hägglund
+	Algorithmic Aspects of Regularity	2000	Yoshiharu Kohayakawa V. Rödl
+	Szemerédi’s Regularity Lemma for Sparse Graphs	1997	Yoshiharu Kohayakawa
+	A sparse regular approximation lemma	2017	Guy Moshkovitz A. Shapira
+	A Sparse Regular Approximation Lemma	2016	Guy Moshkovitz A. Shapira
+	A Sparse Regular Approximation Lemma	2016	Guy Moshkovitz A. Shapira
+	Regularity Lemmas for Graphs	2010	Vojtěch Rödl Mathias Schacht
+ PDF Chat	On Regularity Lemmas and their Algorithmic Applications	2017	Jacob Fox László Lovász Yufei Zhao
+	Regularity and removal lemmas and their applications	2017	László Lovász
+	A Tight Bound for Hyperaph Regularity	2019	Guy Moshkovitz A. Shapira

Works That Cite This (24)

Action	Title	Year	Authors
+	A sparse regular approximation lemma	2017	Guy Moshkovitz A. Shapira
+ PDF Chat	An improved lower bound for arithmetic regularity	2016	Kaave Hosseini Shachar Lovett Guy Moshkovitz A. Shapira
+ PDF Chat	Limitations on regularity lemmas for clustering graphs	2020	Noga Alon Guy Moshkovitz
+ PDF Chat	An improved bound for regular decompositions of 3-uniform hypergraphs of bounded VC2-dimension	2023	C. Terry
+ PDF Chat	Embedding Graphs into Larger Graphs: Results, Methods, and Problems	2019	Miklós Simonovits Endre Szemerédi
+ PDF Chat	A unified view of graph regularity via matrix decompositions	2021	Greg Bodwin Santosh Vempala
+ PDF Chat	A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing	2016	Jacob Fox János Pach Andrew Suk
+	Tower-type bounds for Roth's theorem with popular differences	2020	Jacob Fox Huy Tuan Pham Yufei Zhao
+ PDF Chat	A Tight Bound for Hyperaph Regularity	2019	Guy Moshkovitz A. Shapira
+	Some Cubic Time Regularity Algorithms for Triple Systems	2024	Brendan Nagle John Theado

Works Cited by This (4)

Action	Title	Year	Authors
+	Szemeredi''s Regularity Lemma and its applications in graph theory	1995	János Komlós Miklós Simonovits
+ PDF Chat	Bounds for graph regularity and removal lemmas	2012	David Conlon Jacob Fox
+	Lower bounds of tower type for Szemerédi's uniformity lemma	1997	W. T. Gowers
+	REGULAR PARTITIONS OF GRAPHS	1975	Endre Szemerédi