TY - JOUR

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

AU - Balogh, József

AU - Hu, Ping

AU - Lidický, Bernard

AU - Pfender, Florian

N1 - Funding Information:
We would like to thank Jan Volec for fruitful discussions and two anonymous referees for a careful reading of the manuscript and several suggestions improving the write-up. Research of first author was partially supported by Simons Fellowship ( 263583 ), NSF CAREER Grant DMS-0745185 , Arnold O. Beckman Research Award (UIUC Campus Research Board 13039) and Marie Curie FP7-PEOPLE-2012-IIF 327763. Research of the third author was supported in part by NSF grant DMS-1266016 . Research of fourth author was partially supported by a collaboration grant from the Simons Foundation ( 276726 ).
Publisher Copyright:
© 2015 Elsevier Ltd.

PY - 2016/2/1

Y1 - 2016/2/1

N2 - 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) = a. b. c. d. e + 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 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.

AB - 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) = a. b. c. d. e + 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 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.

UR - http://www.scopus.com/inward/record.url?scp=84942066416&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84942066416&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2015.08.006

DO - 10.1016/j.ejc.2015.08.006

M3 - Article

AN - SCOPUS:84942066416

SN - 0195-6698

VL - 52

SP - 47

EP - 58

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

ER -