Maximizing five-cycles in Kr-free graphs. (October 2021) - Lidický, Bernard; Murphy, Kyle
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 .