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

DOI10.1016/J.EJC.2015.08.006MaRDI QIDQ896063zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

density maximization

Mathematics Subject Classification ID

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

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.

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

Cites work

• A Solution to the 2/3 Conjecture
• A new lower bound based on Gromov's method of selecting heavily covered points
• A problem of Erdős on the minimum number of \(k\)-cliques
• Flag algebras
• Minimum Number of Monotone Subsequences of Length 4 in Permutations
• Minimum Number ofk-Cliques in Graphs with Bounded Independence Number
• Monochromatic triangles in three-coloured graphs
• On possible Turán densities
• On the Caccetta-Häggkvist conjecture with forbidden subgraphs
• On the Maximum Induced Density of Directed Stars and Related Problems
• 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
• Rainbow triangles in three-colored graphs
• The inducibility of blow-up graphs
• The inducibility of graphs
• The inducibility of graphs on four vertices
• Turán \(H\)-densities for 3-graphs
• Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube

Cited in

(31)

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

Describes a project that uses

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)