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

DOI10.1017/S0963548319000257zbMATH Open1436.05045arXiv1803.00165OpenAlexW3099594434WikidataQ127153624 ScholiaQ127153624MaRDI QIDQ5222570FDOQ5222570

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)

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.

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

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

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)

Cites Work

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

Cited In (4)

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

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)