Source-linked AI summary
On the Number of Pentagons in Triangle-Free Graphs
Hamed Hatami, Jan Hladký, Daniel Král, Serguei Norine, Alexander Razborov
TL;DR
The paper asks how many pentagons a triangle-free graph can contain and whether the pentagon blow-up is uniquely extremal. Using flag algebras and related blow-up arguments, it proves the sharp bound, characterizes equality, and handles sufficiently large non-divisible orders. It also notes limitations in resolving the all-orders exact problem.
Problem
The paper addresses Erdős's conjecture that balanced blow-ups of the pentagon maximize pentagon counts among triangle-free graphs.
Method
The authors use flag-algebra calculations together with homomorphism, extension-measure, and blow-up arguments to derive asymptotic and exact conclusions.
Results
Every n-vertex triangle-free graph contains at most (n/5)^5 pentagons, with equality only for n divisible by five and the balanced blow-up of the pentagon; sufficiently large cases are also characterized.
Takeaways & Limitations
The paper settles Erdős's pentagon conjecture in the density sense, gives the exact divisible case, and identifies almost balanced pentagon blow-ups as extremal for sufficiently large n.
Takeaways & Limitations
An exact bound on the maximum number of pentagons for every n remains open, and the original proof claiming to resolve that conjecture contained an uncorrected mistake.
Abstract
from arXiv · showhide
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.
1. Introduction
The paper studies how far triangle-free graphs can depart from bipartiteness, focusing on pentagon counts and Erdős's conjecture that balanced pentagon blow-ups are extremal. It settles the density problem, proves the divisible case exactly, and obtains asymptotic uniqueness and sufficiently-large exact results.
- Triangle-free graphs need not be bipartite, motivating quantitative measures based on induced edges, edge deletions, and pentagon counts.
- Erdős conjectured that balanced blow-ups of the pentagon maximize each of these parameters among triangle-free graphs.
- Earlier work brought the pentagon-density upper bound within factors 1.03 and 1.001 of the conjectured optimum.
- The paper settles the pentagon question in density, implying the exact solution when 5 divides n, and proves asymptotic uniqueness.
- The exact maximum for sufficiently large non-divisible n is treated separately, while an exact bound for every n remains open.
2. Preliminaries
The preliminaries introduce triangle-free flag-algebra notation, types, flags, the upward operator, extension measures, and blow-ups. They also establish the graph-invariant correspondence used later to convert asymptotic information into exact structural conclusions.
- Notation: The paper works in the flag-algebra theory of triangle-free graphs, using models, types, and flags to represent the relevant finite structures.
- Operator πσ, and extension measures: The upward operator πσ maps unlabelled flag-algebra elements into σ-flag algebras and is an algebra homomorphism.
- Operator πσ, and extension measures: An extension measure Pσ extends a positive homomorphism φ and is supported on Sσ(φ), from which φ can be reconstructed.
- Infinite blow-ups: The invariant φG uniquely determines a finite graph up to isomorphism, enabling asymptotic flag-algebra results to support exact graph conclusions.
- Infinite blow-ups: A blow-up G(k) replaces each vertex of G by k independent copies, retaining edges between parts corresponding to edges of G.
- Infinite blow-ups: As blow-up sizes grow, induced-subgraph densities converge to a homomorphism φG; for triangle-free G, this homomorphism remains in the triangle-free theory.
3. Main results
The paper proves the asymptotic pentagon bound for triangle-free graphs and derives exact equality and uniqueness in the divisible case. It also gives the exact non-divisible count and proves the corresponding extremal characterization for sufficiently large n, while noting an unresolved finite-size issue.
- Theorem 3.1: C5 ≤ 5! holds asymptotically in the theory of triangle-free graphs, answering Erdős’s pentagon-density question.The proof uses a direct flag-algebra calculation whose nonnegative summands imply the inequality.
- Corollary 3.3: Every n-vertex triangle-free graph contains at most (n/5)^5 pentagons.This finite bound follows from the asymptotic theorem applied to the infinite blow-up homomorphism.
- Corollary 3.3: Equality occurs only when 5 divides n and the graph is the balanced blow-up of the pentagon.The uniqueness argument identifies the pentagon blow-up homomorphism as the unique extremal limit.
- Non-divisible orders: For n = 5ℓ + a, an almost balanced blow-up of C5 contains χ(n) = ℓ^(5−a)(ℓ + 1)^a pentagons.The paper conjectures that χ(n) is the maximum for every n.
- Non-divisible orders: For sufficiently large n, any triangle-free graph with at least χ(n) pentagons is an almost balanced blow-up of C5.A stability argument establishes this characterization, but the paper does not resolve the conjecture for every finite n.
4. Exact bound
For sufficiently large n, every triangle-free graph with at least χ(n) pentagons must be an almost balanced blow-up of C5. The proof progressively organizes vertices into five near-equal parts and forces the extremal adjacency pattern.
- Exact structural result: Theorem 4.2 states that sufficiently large extremal triangle-free graphs are almost balanced blow-ups of C5.There exists n0 such that any triangle-free graph with n ≥ n0 vertices and at least χ(n) pentagons has this form.
- Approximation and partition: The proof begins by comparing the graph with C5 in cut distance and obtains five parts whose sizes differ from n/5 by at most a controlled error.The argument uses Theorems 4.1 and 3.2 to establish closeness to an almost balanced blow-up, then produces a partition A1,...,A5.
- Cleaning exceptional vertices: Vertices failing the required degree conditions are either reassigned to the five parts or replaced when replacement increases the pentagon count.Maximality implies that each exceptional vertex already lies in at least p1 pentagons, constraining how many such vertices can remain.
- Counting pentagons: After cleaning, every pentagon uses one vertex from each of five parts, so the total count is bounded by the product of their sizes.The induced subgraphs within nonconsecutive parts are empty, forcing every pentagon to meet all five refined parts.
- Equality structure: The product is maximized when all five part sizes differ by at most one, and equality forces complete adjacency between consecutive parts.Thus the graph is an almost balanced blow-up of C5.