A bound on the inducibility of cycles

Abstract

In 1975, Pippenger and Golumbic conjectured that every n-vertex graph has at most $n^k/(k^k-k)$ induced cycles of length k for k at least 5. We prove that every n-vertex graph has at most $2n^k/k^k$ induced cycles of length k.

References in corpus (1)

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

Cited by in corpus (13)

• Anticoncentration for subgraph statistics
• Inducibility of directed paths
• Polynomial to exponential transition in Ramsey theory
• A Completion of the Proof of the Edge-statistics Conjecture
• Stability from graph symmetrisation arguments with applications to inducibility
• The edge-statistics conjecture for $\ell \ll k^{6/5}$
• $C_5$ is almost a fractalizer
• The inducibility of oriented stars
• On the inducibility problem for random Cayley graphs of abelian groups with a few deleted vertices
• Inducibility of 4-vertex tournaments
• Planar graphs with the maximum number of induced 6-cycles
• Inducibility in $H$-free graphs and inducibility of Turán graphs
• Inducibility of rainbow graphs