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

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)=a\cdot b\cdot c\cdot d\cdot e+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.

15 pages, 3 figures

References in corpus (2)

• Minimum number of monotone subsequences of length 4 in permutations
• Rainbow triangles in three-colored graphs

Cited by in corpus (27)

• Rainbow triangles in three-colored graphs
• Anticoncentration for subgraph statistics
• A bound on the inducibility of cycles
• Inducibility of directed paths
• Combinatorial anti-concentration inequalities, with applications
• Polynomial to exponential transition in Ramsey theory
• Elusive extremal graphs
• Semidefinite Programming and Ramsey Numbers
• Closing in on Hill's conjecture
• Decomposing graphs into edges and triangles
• A Completion of the Proof of the Edge-statistics Conjecture
• The edge-statistics conjecture for $\ell \ll k^{6/5}$
• Stability from graph symmetrisation arguments with applications to inducibility
• $C_5$ is almost a fractalizer
• The inducibility of oriented stars
• Minimizing the number of 5-cycles in graphs with given edge-density
• Maximum Number of Almost Similar Triangles in the Plane
• On the inducibility problem for random Cayley graphs of abelian groups with a few deleted vertices
• Asymptotics of Ramsey numbers of double stars
• Finitely forcible graphons with an almost arbitrary structure
• Inducibility of 4-vertex tournaments
• Inducibility of the Net Graph
• Inducibility in $H$-free graphs and inducibility of Turán graphs
• Inducibility of rainbow graphs
• Getting to the Root of the Problem: Sums of Squares for Limits of Trees
• Planar graphs with the maximum number of induced 6-cycles
• Paths of Length Three are $K_{r+1}$-Turán Good