![Real Analysis in Computer Science_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Real%20Analysis%20in%20Computer%20Science_hi-res.jpg?h=e2b42a27&itok=jpgiJZrK)
Abstract
A celebrated result of Gowers states that for every epsilon > 0 there is a graph G so that every epsilon-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/epsilon. 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.