A tight lower bound for Szemerédi's regularity lemma

2014/03/07 by Fox, Jacob, Lovász, László Miklós · 2 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1403.1768

Abstract

Addressing a question of Gowers, we determine the order of the tower height for the partition size in a version of Szemerédi's regularity lemma.

Cited by

• Polynomial Property Testing
• Regularity for hypergraphs with bounded VC₂ dimension

Related

• A Short Proof of Gowers' Lower Bound for the Regularity Lemma
• The Regularity Lemma with bounded VC Dimension
• Improved Bounds for Szemerédi's Theorem
• A tower lower bound for the degree relaxation of the Regularity Lemma
• Bounds for graph regularity and removal lemmas