Minimizing the number of 5-cycles in graphs with given edge-density
Minimizing the number of 5-cycles in graphs with given edge-density
复制标题
最小化给定边密度的图中 5 循环的数量
DOI：
10.1017/s0963548319000257
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
O. Pikhurko
中科院分区：
文献类型：
--
作者：
Patrick Bennett;A. Dudek;Bernard Lidick'y;O. Pikhurko
Abstract Motivated by the work of Razborov about the minimal density of triangles in graphs we study the minimal density of the 5-cycle C 5. We show that every graph of order n and size $ (1 - 1/k) \left( {\matrix{n \cr 2 }} \right) $, where k ≥ 3 is an integer, contains at least $$({1 \over {10}} - {1 \over {2k}} + {1 \over {{k^2}}} - {1 \over {{k^3}}} + {2 \over {5{k^4}}}){n^5} + o({n^5})$$ copies of C5. 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.
Abstract Motivated by the work of Razborov about the minimal density of triangles in graphs we study the minimal density of the 5-cycle C 5. We show that every graph of order n and size $ (1 - 1/k) \left( {\matrix{n \cr 2 }} \right) $, where k ≥ 3 is an integer, contains at least $$({1 \over {10}} - {1 \over {2k}} + {1 \over {{k^2}}} - {1 \over {{k^3}}} + {2 \over {5{k^4}}}){n^5} + o({n^5})$$ copies of C5. 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.