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

Guy Moshkovitz, Asaf Shapira

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…