Article
Maximizing five-cycles in Kr-free graphs
arXiv
Document Type
Article
Disciplines
Publication Version
Submitted Manuscript
Publication Date
7-8-2020
Abstract
The Erdos Pentagon problem asks to find an n-vertex triangle-free graph that is maximizing the number of 5-cycles. The problem was solved using flag algebras by Grzesik and independently by Hatami, Hladky, Kral, Norin, and Razborov. Recently, Palmer suggested the general problem of maximizing the number of 5-cycles in K_{k+1}-free graphs. Using flag algebras, we show that every K_{k+1}-free graph of order n contains at most 110k4(k4−5k3+10k2−10k+4)n5+o(n5)
copies of C_5 for any k≥3, with the Turan graph begin the extremal graph for large enough n.
Copyright Owner
The Authors
Copyright Date
2020
Language
en
File Format
application/pdf
Citation Information
Bernard Lidicky and Kyle Murphy. "Maximizing five-cycles in Kr-free graphs" arXiv (2020) Available at: http://works.bepress.com/bernard-lidicky/64/
This preprint is made available through arXiv: https://arxiv.org/abs/2007.03064.