Minimizing the number of 5-cycles in graphs with given edge-density

DOI10.1017/S0963548319000257MaRDI QIDQ5222570zbMATH OpenOpenAlexWikidataFDO

Authors Patrick Bennett, Andrzej Dudek, Bernard Lidický, Oleg Pikhurko

Publication date 6 April 2020

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.00165

zbMATH Keywords

balanced complete \(k\)-partite graphmatching upper bound

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Paths and cycles (05C38)

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 $$, where $kge3$ is an integer, contains at least [ left( frac{1}{10} -frac{1}{2k} + frac{1}{k^2} - frac{1}{k^3} + frac{2}{5 k^4} ight)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.

Recommendations

• On the maximum number of five-cycles in a triangle-free graph
• Minimum number of edges that occur in odd cycles
• Maximizing five-cycles in \(K_r\)-free graphs
• On the number of pentagons in triangle-free graphs
• Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle

Cites work

• scientific article; zbMATH DE number 3869331 (Why is no real title available?)
• scientific article; zbMATH DE number 4216032 (Why is no real title available?)
• scientific article; zbMATH DE number 3821782 (Why is no real title available?)
• scientific article; zbMATH DE number 3185004 (Why is no real title available?)
• An analytic approach to stability
• Asymptotic structure of graphs with the minimum number of triangles
• CSDP, A C library for semidefinite programming
• Efficient testing of large graphs
• Flag algebras
• Graph removal lemmas
• Introduction to Random Graphs
• Large networks and graph limits
• Limits of dense graph sequences
• Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
• On the Minimal Density of Triangles in Graphs
• On the maximum number of five-cycles in a triangle-free graph
• On the number of pentagons in triangle-free graphs
• On the structure of linear graphs
• Pentagons in triangle-free graphs
• Strong forms of stability from flag algebra calculations
• Testing properties of graphs and functions
• The clique density theorem
• The inducibility of graphs
• The minimum number of triangles in graphs of given order and size
• The number of cliques in graphs of given order and size
• Triangles in an Ordinary Graph

Cited in

(4)

• Paths of length three are \(K_{r+1}\)-Turán-good
• C5 ${C}_{5}$ is almost a fractalizer
• Stability from graph symmetrisation arguments with applications to inducibility
• Maximizing five-cycles in \(K_r\)-free graphs

Describes a project that uses

Uses Software

• CSDP

This page was built for publication: Minimizing the number of 5-cycles in graphs with given edge-density

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5222570)