On the Erdös‐Stone Theorem

for all n large enough with respect to c and d. In a sense, this result is best possible: as shown by Bollobas and Erdos [1], our constant 1/500 cannot be increased beyond 5. Our argument hinges on a theorem asserting that every sufficiently large graph can be partitioned into a small number of classes in such a way that the partition exhibits strong regularity properties. To state the theorem in more precise terms, we need a few definitions. When A and B are nonempty disjoint sets of vertices in some graph then we denote by d{A, B) the density of edges between A and B: this is the number of edges with one endpoint in A and the other endpoint in B divided by \A\-\B\. The pair (A,B) is called E-regular if X £ A, \X\ ^ E\A\, Y <= B and |V| ^ E\B\ imply that \d(X, Y) — d(A,B)\ < E; otherwise the pair is E-irregular. A partition of a set V into classes CO,CX, ...,Ck is called E-regular if |C0| ^ F\V\, |C,| = \Cj\ whenever 1 ^ / < j ^ k and if at most F.k of the pairs (ChCj) with 1 ^ / < j ^ k are <;-irregular. The Regular Partition Theorem, proved in [5], asserts that for every positive E and for every positive integer m there are positive integers M and N with the following property: if the set V of vertices of a graph has size at least N then there is an ^--regular partition of V into k+ 1 classes such that m ^ k ^ M.