For , put , , and . Every graph on vertices satisfiesThus 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
There are currently no matching articles.