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 -