A Short Proof of Gowers' Lower Bound for the Regularity Lemma
summary
Constructs a weighted complete graph with edge weights in [0,1], builds a sequence of partitions X0,X1,... whose cluster counts grow as a tower, then runs 1/√ε iterations adding weight √ε to carefully chosen bipartite subpairs. A key lemma shows any ε-regular partition must become, after repeated refinement, essentially the finest partition up to O(√ε) vertex moves. That forces any ε-regular partition to have size at least a tower-of-exponents of height Ω(1/√ε), giving Gowers‑style lower bounds.
AI-written summary · about