Name
Abstract | ||
|---|---|---|
Fifty years ago Erdos asked to determine the minimum number of k-cliques in a graph on n vertices with independence number less than l. He conjectured that this minimum is achieved by the disjoint union of l-1 complete graphs of size nl-1. This conjecture was disproved by Nikiforov, who showed that the balanced blow-up of a 5-cycle has fewer 4-cliques than the union of 2 complete graphs of size n2. In this paper we solve Erdos@? problem for (k,l)=(3,4) and (k,l)=(4,3). Using stability arguments we also characterize the precise structure of extremal examples, confirming Erdos@? conjecture for (k,l)=(3,4) and showing that a blow-up of a 5-cycle gives the minimum for (k,l)=(4,3). |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.jctb.2013.02.003 | J. Comb. Theory, Ser. B |
Keywords | DocType | Volume |
complete graph,balanced blow-up,size n2,disjoint union,size nl-1,l-1 complete graph,extremal example,minimum number,independence number,fewer 4-cliques | Journal | 103 |
Issue | ISSN | Citations |
3 | 0095-8956 | 8 |
PageRank | References | Authors |
0.58 | 8 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shagnik Das | 1 | 32 | 6.57 |
| Hao Huang | 2 | 589 | 104.49 |
| Jie Ma | 3 | 78 | 15.04 |
| Humberto Naves | 4 | 24 | 4.08 |
| Benny Sudakov | 5 | 1391 | 159.71 |