  We give a proof of Szemeredi's regularity lemma in the special case of a
graph with bounded VC dimension and show that it is possible to obtain "merely"
doubly exponential bounds on the size of the partition in this case.

Combinatorics