Csongor Beke


On the generalised Turán problem for odd cycles

Combinatorics Seminar

6th December 2023, 2:00 pm – 3:00 pm
Fry Building, G.07

In 1984, Erdős conjectured that the number of pentagons in any triangle-free graph on n vertices is at most (n/5)^5 , which is sharp by the balanced blow-up of a pentagon, this was proven using flag algebras. In this talk I will present a non-computational proof of an extension of this result for longer cycles: for each odd k ≥ 7, the balanced blow-up of C_k (uniquely) maximises the number of k-cycles among C_{k-2}-free graphs on n vertices, as long as n is sufficiently large.

Comments are closed.