Department of
Applied
Mathematics

Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle

Ping Hu

Abstract

Let C(n) denote the maximum number of induced copies of 5-cycles in graphs on n vertices. For n large enough, we show that C(n)=abcde + C(a)+C(b)+C(c)+C(d)+C(e), where a+b+c+d+e = n and a,b,c,d,e are as equal as possible. Moreover, for n being a power of 5, we show that the unique graph on n vertices maximizing the number of induced 5-cycles is an iterated blow-up of a 5-cycle. The proof uses flag algebra computations and stability methods.

Joint work with Balogh, Lidický and Pfender.