Choose a fixed sample size for which the normalized Turan theorem bound lies below the given density by a positive margin. The expected edge count in a random -vertex subset then forces a positive proportion of subsets to contain a forbidden-size clique. Each clique belongs to a known number of subsets, so double counting gives a positive constant times cliques.
Articles by others on the same topic
There are currently no matching articles.