Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle

DOI10.1016/J.EJC.2015.08.006zbMATH Open1327.05171arXiv1411.4645OpenAlexW2130182662MaRDI QIDQ896063FDOQ896063

Authors: József Balogh, Ping Hu, Bernard Lidický, Florian Pfender 

Publication date: 11 December 2015

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

Abstract: Let $C(n)$ denote the maximum number of induced copies of 5-cycles in graphs on $n$ vertices. For $n$ large enough, we show that $C(n)=acdotbcdotccdotdcdote+C(a)+C(b)+C(c)+C(d)+C(e)$, where $a+b+c+d+e=n$ and $a,b,c,d,e$ are as equal as possible. Moreover, if $n$ is a power of 5, we show that the unique graph on $n$ vertices maximizing the number of induced 5-cycles is an iterated blow-up of a 5-cycle.

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

Recommendations

• C5 ${C}_{5}$ is almost a fractalizer
• Maximising the number of induced cycles in a graph
• The maximum number of induced C5's in a planar graph
• A bound on the inducibility of cycles
• Maximizing five-cycles in \(K_r\)-free graphs

zbMATH Keywords

density maximization

Mathematics Subject Classification ID

Paths and cycles (05C38) Density (toughness, etc.) (05C42)

Cites Work

• On the number of pentagons in triangle-free graphs
• A Solution to the 2/3 Conjecture
• On possible Turán densities
• Flag algebras
• On the maximum number of five-cycles in a triangle-free graph
• A problem of Erdős and Sós on 3-graphs
• Turán \(H\)-densities for 3-graphs
• Rainbow triangles in three-colored graphs
• On the Minimal Density of Triangles in Graphs
• A new lower bound based on Gromov's method of selecting heavily covered points
• On the Caccetta-Häggkvist conjecture with forbidden subgraphs
• Counting flags in triangle-free digraphs
• The inducibility of graphs
• The inducibility of blow-up graphs
• Monochromatic triangles in three-coloured graphs
• The Inducibility of Graphs on Four Vertices
• Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
• Minimum Number ofk-Cliques in Graphs with Bounded Independence Number
• Minimum Number of Monotone Subsequences of Length 4 in Permutations
• A problem of Erdős on the minimum number of \(k\)-cliques
• On the Maximum Induced Density of Directed Stars and Related Problems

Cited In (31)

• The inducibility of oriented stars
• Anticoncentration for subgraph statistics
• The edge-statistics conjecture for \(\ell \ll k^{6/5} \)
• On the exact maximum induced density of almost all graphs and their inducibility
• Maximising the number of induced cycles in a graph
• On the Caccetta-Häggkvist conjecture with a forbidden transitive tournament
• Minimizing the number of 5-cycles in graphs with given edge-density
• Sharp bounds for decomposing graphs into edges and triangles
• C5 ${C}_{5}$ is almost a fractalizer
• Paths of length three are \(K_{r+1}\)-Turán-good
• On the inducibility of oriented graphs on four vertices
• Maximum number of almost similar triangles in the plane
• The maximum number of induced C5's in a planar graph
• Inducibility of \(d\)-ary trees
• Finitely forcible graphons with an almost arbitrary structure
• On the inducibility problem for random Cayley graphs of abelian groups with a few deleted vertices
• Edge-statistics on large graphs
• Semidefinite Programming and Ramsey Numbers
• Planar graphs with the maximum number of induced 6-cycles
• Strong forms of stability from flag algebra calculations
• On the maximum number of odd cycles in graphs without smaller odd cycles
• Further results on the inducibility of $d$-ary trees
• Inducibility of directed paths
• On the inducibility of cycles
• On the inducibility of cycles
• Stability from graph symmetrisation arguments with applications to inducibility
• Rainbow triangles in three-colored graphs
• Decomposing Graphs into Edges and Triangles
• A bound on the inducibility of cycles
• Compactness and finite forcibility of graphons
• Closing in on Hill's Conjecture

Uses Software

• SageMath
• Flagmatic

This page was built for publication: Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle

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