Source-linked AI summary
On the maximum number of five-cycles in a triangle-free graph
Andrzej Grzesik
TL;DR
The paper addresses Erdős's conjecture on the maximum number of 5-cycles in a triangle-free graph. Using Razborov's flag-algebra method and semidefinite programming, it proves the conjectured bound and thereby settles the conjecture affirmatively.
Problem
Erdős conjectured that a triangle-free graph of order n contains at most (n/5)^5 cycles of length five.
Method
The paper applies Razborov's flag algebras and bounds the relevant Turán density through a semidefinite programming problem with positive semidefinite matrices.
Results
πC5(K3) ≤ 24/625, yielding the stated upper bound on the number of 5-cycles in triangle-free graphs.
Takeaways & Limitations
The result settles Erdős's pentagon conjecture in the affirmative.
Takeaways & Limitations
The certificate maximizes over coefficients whose associated matrices P, Q, and R are positive semidefinite.
Abstract
from arXiv · showhide
Using Razborov's flag algebras we show that a triangle-free graph on n vertices contains at most (n/5)^5 cycles of length five. It settles in the affirmative a conjecture of Erdos.