Pentagons in triangle-free graphs

Date
2018-12-01
Authors
Lidicky, Bernard
Pfender, Florian
Lidicky, Bernard
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Mathematics
Organizational Unit
Journal Issue
Series
Department
Mathematics
Abstract

For all n≥9, we show that the only triangle-free graphs on n vertices maximizing the number 5-cycles are balanced blow-ups of a 5-cycle. This completely resolves a conjecture by Erd\H{o}s, and extends results by Grzesik and Hatami, Hladky, Kral, Norin and Razborov, where they independently showed this same result for large n and for all n divisible by 5.

Comments

This is a manuscript of an article published as Lidický, Bernard, and Florian Pfender. "Pentagons in triangle-free graphs." European Journal of Combinatorics 74 (2018): 85-89. doi: 10.1016/j.ejc.2018.07.008. Posted with permission.

Description
Keywords
Citation
DOI
Collections