A Short Proof of Gowers' Lower Bound for the Regularity Lemma

Abstract

A celebrated result of Gowers states that for every ε> 0 there is a graph G so that every ε-regular partition of G (in the sense of Szemeredi's regularity lemma) has order given by a tower of exponents of height polynomial in 1/ε. In this note we give a new proof of this result that uses a construction and proof of correctness that are significantly simpler and shorter.

Cited by in corpus (2)

• Approximating the rectilinear crossing number
• Semi-algebraic colorings of complete graphs