For , put , , and . Every graph on vertices satisfies
Thus an edge count forces at least triangles in a graph. This is an exact finite bound, with the rounding in the Turan graph retained. To prove it, use edge-triangle symmetrization. The inequality allows merging the two smallest classes when there are at least four classes. With three classes, fixing the middle class makes the objective affine in the product of the other two sizes; either merge them or balance them. Only and need remain.

Articles by others on the same topic (0)

There are currently no matching articles.