1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Generalized Turán Problems for Small Graphs

Published Online: 21 Jan 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 29 Jun 2020
Accepted: 17 Nov 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

For graphs H and F, the generalized Turán number ex(n, H, F) is the largest number of copies of H in an F -free graph on n vertices. We consider this problem when both H and F have at most four vertices. We give sharp results in almost all cases, and connect the remaining cases to well-known unsolved problems. Our main new contribution is applying the progressive induction method of Simonovits for generalized Turán problems.

Keywords

MSC 2010

[1] N. Alon and C. Shikhelman, Many T copies in H-free graphs, J. Combin. Theory Ser. B 121 (2016) 146–172. doi:10.1016/j.jctb.2016.03.00410.1016/j.jctb.2016.03.004Search in Google Scholar

[2] B. Bollobás and E. Győri, Pentagons vs. triangles, Discrete Math. 308 (2008) 4332–4336. doi:10.1016/j.disc.2007.08.01610.1016/j.disc.2007.08.016Search in Google Scholar

[3] J.I. Brown and A. Sidorenko, The inducibility of complete bipartite graphs, J. Graph Theory 18 (1994) 629–645. doi:10.1002/jgt.319018061010.1002/jgt.3190180610Search in Google Scholar

[4] D. Chakraborti and D.Q. Chen, Exact results on generalized Erdős-Gallai problems. arXiv:2006.04681 (2020)Search in Google Scholar

[5] S. Cambie, R. de Verclos and R. Kang, Regular Turán numbers and some Gan-Loh-Sudakov-type problems. arXiv:1911.08452 (2019)Search in Google Scholar

[6] Z. Chase, A proof of the Gan-Loh-Sudakov conjecture. arXiv:1911.08452 (2019)Search in Google Scholar

[7] P. Erdős and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10 (1959) 337–356. doi:10.1007/BF0202449810.1007/BF02024498Search in Google Scholar

[8] P. Erdős and M. Simonovits, On a valence problem in extremal graph theory, Discrete Math. 5 (1973) 323–334. doi:10.1016/0012-365X(73)90126-X10.1016/0012-365X(73)90126-XSearch in Google Scholar

[9] R.J. Faudree and R.H. Schelp, Path Ramsey numbers in multicolorings, J. Combin. Theory Ser. B 19 (1975) 150–160. doi:10.1016/0095-8956(75)90080-510.1016/0095-8956(75)90080-5Search in Google Scholar

[10] Z. Füredi, On the number of edges of quadrilateral-free graphs, J. Combin. Theory Ser. B 68 (1996) 1–6. doi:10.1006/jctb.1996.005210.1006/jctb.1996.0052Search in Google Scholar

[11] Z. Füredi, New asymptotics for bipartite Turán numbers, J. Combin. Theory Ser. A 75 (1996) 141–144. doi:10.1006/jcta.1996.006710.1006/jcta.1996.0067Search in Google Scholar

[12] W. Gan, P. Loh and B. Sudakov, Maximizing the number of independent sets of a fixed size, Combin. Probab. Comput. 24 (2015) 521–527. doi:10.1017/S096354831400054610.1017/S0963548314000546Search in Google Scholar

[13] D. Gerbner, E. Győri, A. Methuku and M. Vizer, Generalized Turán numbers for even cycles, J. Combin. Theory Ser. B 145 (2020) 169–213. doi:10.1016/j.jctb.2020.05.00510.1016/j.jctb.2020.05.005Search in Google Scholar

[14] D. Gerbner, E. Győri, A. Methuku and M. Vizer, Induced generalized Turán numbers, manuscript.Search in Google Scholar

[15] D. Gerbner, A. Methuk and M. Vizer, Generalized Turán problems for disjoint copies of graphs, Discrete Math. 342 (2019) 3130–3141. doi:10.1016/j.disc.2019.06.02210.1016/j.disc.2019.06.022Search in Google Scholar

[16] D. Gerbner and C. Palmer, Counting copies of a fixed subgraph of F -free graph, European J. Math. 82 (2019) 103001. doi:10.1016/j.ejc.2019.10300110.1016/j.ejc.2019.103001Search in Google Scholar

[17] D. Gerbner and C. Palmer, Some exact results for generalized Turán problems. arXiv:2006.03756 (2020)Search in Google Scholar

[18] L. Gishboliner and A. Shapira, A generalized Turán problem and its applications, in: Proc. STOC 2018 Theory Fest: 50th Annual ACM Symposium on the Theory of Computing, June 25–29, 2018 in Los Angeles, CA (2018) 760–772.Search in Google Scholar

[19] A. Grzesik, On the maximum number of five-cycles in a triangle-free graph, J. Combin. Theory Ser. B 102 (2012) 1061–1066. doi:10.1016/j.jctb.2012.04.00110.1016/j.jctb.2012.04.001Search in Google Scholar

[20] E. Győri, J. Pach and M. Simonovits, On the maximal number of certain subgraphs in Kr-free graphs, Graphs Combin. 7 (1991) 31–37. doi:10.1007/BF0178946110.1007/BF01789461Search in Google Scholar

[21] E. Győri, N. Salia, C. Tompkins and O. Zamora, The maximum number of Pl copies in Pk-free graphs, Acta Math. Univ. Comenian. 88 (2019) 773–778.Search in Google Scholar

[22] H. Hatami, J. Hladký, D. Král, S. Norine and A. Razborov, On the number of pentagons in triangle-free graphs, J. Combin. Theory Ser. A 120 (2013) 722–732. doi:10.1016/j.jcta.2012.12.00810.1016/j.jcta.2012.12.008Search in Google Scholar

[23] J. Ma and Y. Qiu, Some sharp results on the generalized Turán numbers, European J. Combin. 84 (2018) 103026. doi:/10.1016/j.ejc.2019.103026Search in Google Scholar

[24] I.Z. Ruzsa and E. Szemerédi, Triple systems with no six points carrying three triangles, Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai 18 (1976) 939–945.Search in Google Scholar

[25] M. Simonovit, A method for solving extremal problems in graph theory, stability problems, in: Theory of Graphs (Proc. Colloq., Tihany, 1966), (Academic Press, New York, 1968) 279–319.Search in Google Scholar

[26] P. Turán, On an extremal problem in graph theory, Matematikai és Fizikai Lapok 48 (1941) 436–452, in Hungarian.Search in Google Scholar

[27] J. Wang, The maximum number of cliques in graphs without large matchings. arXiv:1812.01832 (2018)Search in Google Scholar

[28] A.A. Zykov, On some properties of linear complexes, Matematicheskii Sbornik 66 (1949) 163–188.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo