Maximizing five-cycles in K_r-free graphs

DOI10.1016/J.EJC.2021.103367zbMATH Open1469.05088arXiv2007.03064OpenAlexW3167439620MaRDI QIDQ2048348FDOQ2048348

Authors: Bernard Lidický, Kyle Murphy 

Publication date: 5 August 2021

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: The ErdH{o}s Pentagon problem asks to find an $n$-vertex triangle-free graph that is maximizing the number of $5$-cycles. The problem was solved using flag algebras by Grzesik and independently by Hatami, Hladk'{y}, Kr'{a}l', Norin, and Razborov. Recently, Palmer suggested the general problem of maximizing the number of $5$-cycles in $K_{k+1}$-free graphs. Using flag algebras, we show that every $K_{k+1}$-free graph of order $n$ contains at most [frac{1}{10k^4}(k^4 - 5k^3 + 10k^2 - 10k + 4)n^5 + o(n^5)] copies of $C_5$ for any $kgeq3$, with the Tur'an graph begin the extremal graph for large enough $n$.

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

Recommendations

• On the maximum number of five-cycles in a triangle-free graph
• Minimizing the number of 5-cycles in graphs with given edge-density
• Almost resolvable maximum packings of complete graphs with 5-cycles
• On maximum independent sets in \(P_{5}\)-free graphs
• Some results on \(k\)-critical \(P_5\)-free graphs
• A note on the maximum number of triangles in a \(C_5\)-free graph
• A note on the maximum number of triangles in a C₅‐free graph
• Minimum coverings of the complete graph with 5-cycles
• Constructions of \(k\)-critical \(P_5\)-free graphs
• Optimization and Recognition for K 5-minor Free Graphs in Linear Time

zbMATH Keywords

extremal graph theorytriangle-free graphspentagon density

Mathematics Subject Classification ID

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

Cites Work

• On the number of pentagons in triangle-free graphs
• Hypergraphs do jump
• Applications of the Semi-Definite Method to the Turán Density Problem for 3-Graphs
• Flag algebras
• On the maximum number of five-cycles in a triangle-free graph
• Efficient testing of large graphs
• The minimum size of 3-graphs without a 4-set spanning no or exactly three edges
• Title not available (Why is that?)
• Pentagons vs. triangles
• On the number of \(C_ 5's\) in a triangle-free graph
• Minimum Number of Monotone Subsequences of Length 4 in Permutations
• Title not available (Why is that?)
• Many \(T\) copies in \(H\)-free graphs
• Pentagons in triangle-free graphs
• General lemmas for Berge-Turán hypergraph problems
• On Berge-Ramsey problems
• Inducibility of directed paths
• On the maximal number of certain subgraphs in \(K_ r\)-free graphs
• A note on the maximum number of triangles in a C₅‐free graph
• Generalized Turán problems for even cycles
• A generalized Turán problem and its applications
• Counting copies of a fixed subgraph in \(F\)-free graphs
• Flag Algebras: A First Glance
• Cycles of length 5 in triangle-free graphs: a sporadic counterexample to a characterization of equality
• Sharp bounds for decomposing graphs into edges and triangles
• Minimizing the number of 5-cycles in graphs with given edge-density

Cited In (16)

• Supersaturation for subgraph counts
• Optimization and Recognition for K 5-minor Free Graphs in Linear Time
• Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
• On the maximum number of five-cycles in a triangle-free graph
• Minimizing the number of 5-cycles in graphs with given edge-density
• C5 ${C}_{5}$ is almost a fractalizer
• Paths of length three are \(K_{r+1}\)-Turán-good
• Every graph is eventually Turán-good
• On the generalized Turán problem for odd cycles
• Pentagons in triangle-free graphs
• On the number of pentagons in triangle-free graphs
• The optimal drawings of \(K_{5,n}\)
• Subgraph densities in \(K_r\)-free graphs
• The cycle of length four is strictly \(F\)-Turán-good
• On generalized Turán numbers of intersecting cliques
• Some exact results for non-degenerate generalized Turán problems

Uses Software

• Flagmatic

This page was built for publication: Maximizing five-cycles in \(K_r\)-free graphs

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