Name
Abstract | ||
|---|---|---|
Motivated by the work of Razborov about the minimal density of triangles in graphs we study the minimal density of the 5-cycle C5. We show that every graph of order n and size (1- 1/k)(n 2), where k >= 3 is an integer, contains at least(1/10 - 1/2k + 1/k2 - 1/k3 + 2/5k(4))n(5) + o(n(5))copies of C-5. This bound is optimal, since a matching upper bound is given by the balanced complete k-partite graph. The proof is based on the flag algebras framework. We also provide a stability result. An SDP solver is not necessary to verify our proofs. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1017/S0963548319000257 | COMBINATORICS PROBABILITY & COMPUTING |
DocType | Volume | Issue |
Journal | 29 | 1 |
ISSN | Citations | PageRank |
0963-5483 | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| P BENNETT | 1 | 15 | 5.42 |
| Andrzej Dudek | 2 | 114 | 23.10 |
| Bernard Lidický | 3 | 0 | 1.01 |
| Oleg Pikhurko | 4 | 318 | 47.03 |