Clique supersaturation by sampling

ID: clique-supersaturation-by-sampling

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.

New to topics? Read the docs here!