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

DOI10.1007/s00493-014-3166-4zbMath1399.05128arXiv1308.5352OpenAlexW2160594140WikidataQ124990088 ScholiaQ124990088MaRDI QIDQ682130

Guy Moshkovitz, Asaf Shapira

Publication date: 13 February 2018

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1308.5352

zbMATH Keywords

regularity lemmaequipartitiontower of exponents

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Extremal combinatorics (05D99)

Related Items

Tower-type bounds for Roth's theorem with popular differences ⋮ A unified view of graph regularity via matrix decompositions ⋮ A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing ⋮ An improved lower bound for arithmetic regularity ⋮ Some Cubic Time Regularity Algorithms for Triple Systems ⋮ Local-vs-global combinatorics ⋮ On Regularity Lemmas and their Algorithmic Applications ⋮ Limitations on regularity lemmas for clustering graphs ⋮ Efficient Testing without Efficient Regularity ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ A sparse regular approximation lemma ⋮ Approximating the rectilinear crossing number ⋮ A tight bound for hypergraph regularity

Cites Work

• Unnamed Item
• Lower bounds of tower type for Szemerédi's uniformity lemma
• Bounds for graph regularity and removal lemmas