Minimum Number of k-Cliques in Graphs with Bounded Independence Number

Abstract

Erdos asked in 1962 about the value of f(n,k,l), the minimum number of k-cliques in a graph of order n and independence number less than l. The case (k,l)=(3,3) was solved by Lorden. Here we solve the problem (for all large n) when (k,l) is (3,4), (3,5), (3,6), (3,7), (4,3), (5,3), (6,3), and (7,3). Independently, Das, Huang, Ma, Naves, and Sudakov did the cases (k,l)=(3,4) and (4,3).

25 pages. v4: Three new solved cases added: (3,5), (3,6), (3,7). All calculations are done with Version 2.0 of Flagmatic now

References in corpus (1)

• The codegree threshold for 3-graphs with independent neighbourhoods

Cited by in corpus (7)

• Phase transitions in a complex network
• The Asymptotics of Large Constrained Graphs
• Counting monochromatic copies of K_4: a new lower bound for the Ramsey multiplicity problem
• Asymptotic Structure of Constrained Exponential Random Graph Models
• A new bound for the 2/3 conjecture
• On the 3-local profiles of graphs
• Graphs with few 3-cliques and 3-anticliques are 3-universal