Minimum Number ofk-Cliques in Graphs with Bounded Independence Number
- 1 October 2013
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 22 (6) , 910-934
Abstract
Erdős asked in 1962 about the value off(n,k,l), the minimum number ofk-cliques in a graph with ordernand independence number less thanl. The case (k,l)=(3,3) was solved by Lorden. Here we solve the problem (for all largen) for (3,l) with 4 ≤l≤ 7 and (k,3) with 4 ≤k≤ 7. Independently, Das, Huang, Ma, Naves and Sudakov resolved the cases (k,l)=(3,4) and (4,3).Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- On the number of pentagons in triangle-free graphsJournal of Combinatorial Theory, Series A, 2013
- Applications of the Semi-Definite Method to the Turán Density Problem for 3-GraphsCombinatorics, Probability and Computing, 2012
- The minimum size of 3-graphs without a 4-set spanning no or exactly three edgesEuropean Journal of Combinatorics, 2011
- Hypergraphs Do JumpCombinatorics, Probability and Computing, 2010
- On 3-Hypergraphs with Forbidden 4-Vertex ConfigurationsSIAM Journal on Discrete Mathematics, 2010
- On the Minimum Number of k-Cliques in Graphs with Restricted Independence NumberCombinatorics, Probability and Computing, 2001
- Efficient Testing of Large GraphsCombinatorica, 2000
- On the maximal triangle-free edge-chromatic graphs in three colorsJournal of Combinatorial Theory, 1968
- Blue-Empty Chromatic GraphsThe American Mathematical Monthly, 1962
- On Sets of Acquaintances and Strangers at any PartyThe American Mathematical Monthly, 1959