On the Generalized Turán Problem for Odd Cycles
Csongor Beke, Oliver Janzer
Source abstract
Abstract. In 1984, Erdős conjectured that the number of pentagons in any triangle-free graph on [Formula: see text] vertices is at most [Formula: see text], which is sharp by the balanced blow-up of a pentagon. This was proved by Grzesik, and independently by Hatami et al. As an extension of this result for longer cycles, we prove that for each odd [Formula: see text], the balanced blow-up of [Formula: see text] (uniquely) maximizes the number of [Formula: see text]-cycles among [Formula: see text]-free graphs on [Formula: see text] vertices, as long as [Formula: see text] is sufficiently large. We also show that this is no longer true if [Formula: see text] is not assumed to be sufficiently large. Our result strengthens results of Grzesik and Kielak who proved that for each odd [Formula: see text], the balanced blow-up of [Formula: see text] maximizes the number of [Formula: see text]-cycles among graphs with a given number of vertices and no odd cycles of length less than [Formula: see text]. We further show that if [Formula: see text] and [Formula: see text] are odd and [Formula: see text] is sufficiently large compared to [Formula: see text], then the balanced blow-up of [Formula: see text] does not asymptotically maximize the number of [Formula: see text]-cycles among [Formula: see text]-free graphs on [Formula: see text] vertices. This disproves a conjecture of Grzesik and Kielak.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.