$C_5$ is almost a fractalizer

Abstract

We determine the maximum number of induced copies of a 5-cycle in a graph on $n$ vertices for every $n$. Every extremal construction is a balanced iterated blow-up of the 5-cycle with the possible exception of the smallest level where for $n=8$, the Möbius ladder achieves the same number of induced 5-cycles as the blow-up of a 5-cycle on 8 vertices. This result completes work of Balogh, Hu, Lidický, and Pfender [Eur. J. Comb. 52 (2016)] who proved an asymptotic version of the result. Similarly to their result, we also use the flag algebra method but we extend its use to small graphs.

arXiv comment24 pages, minor corrections

References in corpus (9)

• Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle
• A Note on the Inducibility of 4-vertex Graphs
• A bound on the inducibility of cycles
• Pentagons in triangle-free graphs
• Inducibility of directed paths
• Polynomial to exponential transition in Ramsey theory
• Decomposing graphs into edges and triangles
• Minimizing the number of 5-cycles in graphs with given edge-density
• Inducibility of the Net Graph

Cited by in corpus (2)

• Inducibility of rainbow graphs
• Getting to the Root of the Problem: Sums of Squares for Limits of Trees