DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

Title:

Generalized Turán problems for small graphs

PDF

Source:

Discussiones Mathematicae Graph Theory 43(2) (2023) 549-572

Received: 2020-06-29 , Revised: 2020-11-16 , Accepted: 2020-11-17 , Available online: 2021-01-02 , https://doi.org/10.7151/dmgt.2388

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:

generalized Turán problem, extremal

References:

  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 $K_r$-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 $P_l$ copies in $P_k$-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.
Close