On the Number of Pentagons in Triangle-Free Graphs

Abstract

Using the formalism of flag algebras, we prove that every triangle-free graph $G$ with $n$ vertices contains at most $(n/5{)}^5$ cycles of length five. Moreover, the equality is attained only when $n$ is divisible by five and $G$ is the balanced blow-up of the pentagon. We also compute the maximal number of pentagons and characterize extremal graphs in the non-divisible case provided $n$ is sufficiently large. This settles a conjecture made by Erdős in 1984.

16 pages, accepted to Journal of Combinatorial Theory Ser. A

Cited by in corpus (46)

• Counting copies of a fixed subgraph in $F$-free graphs
• Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
• Non-three-colorable common graphs exist
• Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle
• Asymptotic Structure of Graphs with the Minimum Number of Triangles
• Minimum number of monotone subsequences of length 4 in permutations
• Rainbow triangles in three-colored graphs
• Extensions of Erdős-Gallai Theorem and Luo's Theorem with Applications
• Pentagons in triangle-free graphs
• Inducibility of directed paths
• Minimum Number of k-Cliques in Graphs with Bounded Independence Number
• Maximizing five-cycles in $K_r$-free graphs
• Infinite dimensional finitely forcible graphon
• Every graph is eventually Turán-good
• Polynomial to exponential transition in Ramsey theory
• Elusive extremal graphs
• Closing in on Hill's conjecture
• The Inducibility of Graphs on Four Vertices
• Semidefinite Programming and Ramsey Numbers
• Homomorphism counts in robustly sparse graphs
• The inducibility of blow-up graphs
• The maximum number of cliques in graphs without long cycles
• On the algebraic and topological structure of the set of Turán densities
• More about sparse halves in triangle-free graphs
• Counting multiple graphs in generalized Turán problems
• Minimizing the number of 5-cycles in graphs with given edge-density
• On the maximum number of five-cycles in a triangle-free graph
• A new bound for the 2/3 conjecture
• Resolving sets for breaking symmetries of graphs
• Some extremal results on K_{s,t}-free graphs
• Flag Algebras: A First Glance
• Finitely forcible graph limits are universal
• Densities of 3-vertex graphs
• Finitely forcible graphons with an almost arbitrary structure
• Extremal problems of double stars
• On the number of $k$-gons in finite projective planes
• Triangle Ramsey numbers of complete graphs
• On the density of triangles and squares in regular finite and unimodular random graphs
• Finitely forcible graphons and permutons
• The dimension of the feasible region of pattern densities
• Inducibility in $H$-free graphs and inducibility of Turán graphs
• On the number of cycles in a graph with restricted cycle lengths
• Planar polynomials and an extremal problem of Fischer and Matousek
• Many $T$ copies in $H$-free graphs
• $H$-free subgraphs of dense graphs maximizing the number of cliques and their blow-ups
• Paths of Length Three are $K_{r+1}$-Turán Good