On 03.09.2015 at 12:20 in S4, there is the following noon lecture:
Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle
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.
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010