Minimum Number of k-Cliques in Graphs with Bounded Independence Number
Author:
Preprint
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) when (k,l) is (3,4), (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). More recently, Vaughan solved the problem when k=3 and 5\le l\le 7.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Monochromatic triangles in three-coloured graphsJournal of Combinatorial Theory, Series B, 2013
- On the number of pentagons in triangle-free graphsJournal of Combinatorial Theory, Series A, 2013
- Hypergraphs Do JumpCombinatorics, Probability and Computing, 2010
- On 3-Hypergraphs with Forbidden 4-Vertex ConfigurationsSIAM Journal on Discrete Mathematics, 2010
- On a Problem of Formal Logic2009
- Flag algebrasThe Journal of Symbolic Logic, 2007
- Efficient Testing of Large GraphsCombinatorica, 2000
- On the maximal triangle-free edge-chromatic graphs in three colorsJournal of Combinatorial Theory, 1968