Geodesic
Generalized Turán problems for small graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 549-572

Voir la notice de l'article provenant de la source Library of Science

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: generalized Turán problem, extremal 
Gerbner, Dániel. Generalized Turán problems for small graphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 549-572. http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a15/
@article{DMGT_2023_43_2_a15,
     author = {Gerbner, D\'aniel},
     title = {Generalized {Tur\'an} problems for small graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {549--572},
     year = {2023},
     volume = {43},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a15/}
}
TY  - JOUR
AU  - Gerbner, Dániel
TI  - Generalized Turán problems for small graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 549
EP  - 572
VL  - 43
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a15/
LA  - en
ID  - DMGT_2023_43_2_a15
ER  - 
%0 Journal Article
%A Gerbner, Dániel
%T Generalized Turán problems for small graphs
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 549-572
%V 43
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a15/
%G en
%F DMGT_2023_43_2_a15

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

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

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

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

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

[6] Z. Chase, A proof of the Gan-Loh-Sudakov conjecture (2019). arXiv: 1911.0845

[7] P. Erdős and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10 (1959) 337–356. https://doi.org/10.1007/BF02024498

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

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

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

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

[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. https://doi.org/10.1017/S0963548314000546

[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. https://doi.org/10.1016/j.jctb.2020.05.005

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

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

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

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

[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.

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

[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. https://doi.org/10.1007/BF01789461

[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.

[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. https://doi.org/10.1016/j.jcta.2012.12.008

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

[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.

[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.

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

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

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