Abstract | ||
---|---|---|
Fifty years ago Erdős 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. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1016/j.jctb.2013.02.003 | Journal of Combinatorial Theory, Series B |
Keywords | Field | DocType |
Erdősʼ conjecture,Clique density,Flag algebras | Discrete mathematics,Graph,Combinatorics,Independence number,Vertex (geometry),Lonely runner conjecture,Disjoint union,Collatz conjecture,Conjecture,Erdős–Gyárfás conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
103 | 3 | 0095-8956 |
Citations | PageRank | References |
2 | 0.44 | 9 |
Authors | ||
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 |