Maximizing five-cycles in Kr-free graphs. (October 2021)

• Record Type: Journal Article
• Authors: Lidický, Bernard; Murphy, Kyle
• Is Part Of: European journal of combinatorics. Volume 97(2021)
• Publication Date: 2021-10
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2021.103367
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: The Pentagon Problem of Erdős 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, Hladký, Král', Norin, and Razborov. Recently, Palmer suggested a more 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 1 10 k 4 ( k 4 − 5 k 3 + 10 k 2 − 10 k + 4 ) n 5 + o ( n 5 ) copies of C 5 for any k ≥ 3, with the Turán graph being the extremal graph for large enough n .