[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Supersaturation for Subgraph Counts

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

The classical extremal problem is that of computing the maximum number of edges in an F-free graph. In particular, Turán’s theorem entirely resolves the case where \(F=K_{r+1}\). Later results, known as supersaturation theorems, proved that in a graph containing more edges than the extremal number, there must also be many copies of \(K_{r+1}\). Alon and Shikhelman introduced a broader class of extremal problems, asking for the maximum number of copies of a graph T in an F-free graph (so that \(T=K_2\) is the classical extremal number). In this paper we determine some of these generalized extremal numbers when T and F are stars or cliques and prove some supersaturation results for them.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

Availability of data and material

Not applicable.

Code availability

Not applicable.

References

  1. Alon, N., Shikhelman, C.: Many \(T\) copies in \(H\)-free graphs. J. Combin. Theory Ser. B 121, 146–172 (2016)

    Article  MathSciNet  Google Scholar 

  2. Bollobás, B.: On complete subgraphs of different orders. Math. Proc. Camb. Philos. Soc. 79(1), 19–24 (1976)

    Article  MathSciNet  Google Scholar 

  3. Bollobás, B., Nikiforov, V.: Degree powers in graphs with forbidden subgraphs. Electron. J. Combin. 11(1), 8 (2004). Research Paper 42. http://www.combinatorics.org/Volume_11/Abstracts/v11i1r42.html

  4. Caro, Y., Yuster, R.: A Turán type problem concerning the powers of the degrees of a graph. Electron. J. Combin. 7, 14 (2000). Research Paper 47. http://www.combinatorics.org/Volume_7/Abstracts/v7i1r47.html

  5. Chase, Z.: The maximum number of triangles in a graph of given maximum degree. Adv. Comb. 10, 5 (2020). https://doi.org/10.19086/aic.16788

    Article  MathSciNet  MATH  Google Scholar 

  6. Engbers, J., Galvin, D.: Counting independent sets of a fixed size in graphs with a given minimum degree. J. Graph Theory 76(2), 149–168 (2014). https://doi.org/10.1002/jgt.21756

    Article  MathSciNet  MATH  Google Scholar 

  7. Erdős, P.: Some theorems on graphs. Riveon Lematematika 9, 13–17 (1955)

    MathSciNet  Google Scholar 

  8. Erdős, P.: On a theorem of Rademacher–Turán. Ill. J. Math. 6, 122–127 (1962). http://projecteuclid.org/euclid.ijm/1255631811

  9. Erdős, P.: On the number of complete subgraphs contained in certain graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl. 7, 459–464 (1962)

    MathSciNet  MATH  Google Scholar 

  10. Erdős, P.: Extremal problems in graph theory. In: Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), pp. 29–36. Publ. House Czechoslovak Acad. Sci., Prague (1964)

  11. Erdős, P., Stone, A.H.: On the structure of linear graphs. Bull. Am. Math. Soc. 52, 1087–1091 (1946)

    Article  MathSciNet  Google Scholar 

  12. Füredi, Z.: New asymptotics for bipartite Turán numbers. J. Combin. Theory Ser. A 75(1), 141–144 (1996)

    Article  MathSciNet  Google Scholar 

  13. Gan, W., Loh, P.S., Sudakov, B.: Maximizing the number of independent sets of a fixed size. Combin. Probab. Comput. 24(3), 521–527 (2015). https://doi.org/10.1017/S0963548314000546

    Article  MathSciNet  MATH  Google Scholar 

  14. Gerbner, D., Patkós, B.: Generalized Turán problems for complete bipartite graphs (2021) (under review)

  15. Győri, E., Salia, N., Tompkins, C., Zamora, O.: The maximum number of \(P_\ell\) copies in \(P_k\)-free graphs. Acta Math. Univ. Comenian. (N.S.) 88(3), 773–778 (2019)

    MathSciNet  MATH  Google Scholar 

  16. Györi, E., Pach, J., Simonovits, M.: On the maximal number of certain subgraphs in \(k_r\)-free graphs. Graphs Comb. 7(1), 31–37 (1991). https://doi.org/10.1007/BF01789461

    Article  Google Scholar 

  17. Halfpap, A., Palmer, C.: On supersaturation and stability for generalized Turán problems. J Graph Theor. 97(2), 232–240 (2021). https://doi.org/10.1002/jgt.22652

    Article  Google Scholar 

  18. Lidický, B., Murphy, K.: Maximizing five-cycles in \(k_r\)-free graphs. Eur J Combin. (2021). https://doi.org/10.1016/j.ejc.2021.103367

    Article  MATH  Google Scholar 

  19. Lovász, L.: Combinatorial Problems and Exercises, 2nd edn. AMS Chelsea Publishing, Providence (2007). https://doi.org/10.1090/chel/361

    Book  MATH  Google Scholar 

  20. Lovász, L., Simonovits, M.: On the number of complete subgraphs of a graph, pp. 431–441. Congressus Numerantium, No. XV (1976)

  21. Lovász, L., Simonovits, M.: On the number of complete subgraphs of a graph. II. In: Studies in Pure Mathematics, pp. 459–495. Basel, Birkhäuser (1983)

    Chapter  Google Scholar 

  22. Luo, R.: The maximum number of cliques in graphs without long cycles. J. Combin. Theory Ser. B 128, 219–226 (2018). https://doi.org/10.1016/j.jctb.2017.08.005

    Article  MathSciNet  MATH  Google Scholar 

  23. Moon, J.W., Moser, L.: On a problem of Turán. Magyar Tud. Akad. Mat. Kutató Int. Közl. 7, 283–286 (1962)

    MathSciNet  MATH  Google Scholar 

  24. Nikiforov, V.: Graphs with many \(r\)-cliques have large complete \(r\)-partite subgraphs. Bull. Lond. Math. Soc. 40(1), 23–25 (2008)

    Article  MathSciNet  Google Scholar 

  25. Nikiforov, V.: The number of cliques in graphs of given order and size. Trans. Am. Math. Soc. 363(3), 1599–1618 (2011). https://doi.org/10.1090/S0002-9947-2010-05189-X

    Article  MathSciNet  MATH  Google Scholar 

  26. Pikhurko, O., Yilma, Z.B.: Supersaturation problem for color-critical graphs. J. Combin. Theory Ser. B 123, 148–185 (2017). https://doi.org/10.1016/j.jctb.2016.12.001

    Article  MathSciNet  MATH  Google Scholar 

  27. Rademacher, H.: unpublished (1941)

  28. Razborov, A.A.: On the minimal density of triangles in graphs. Combin. Probab. Comput. 17(4), 603–618 (2008). https://doi.org/10.1017/S0963548308009085

    Article  MathSciNet  MATH  Google Scholar 

  29. Reiher, C.: The clique density theorem. Ann. Math. (2) 184(3), 683–707 (2016). https://doi.org/10.4007/annals.2016.184.3.1

    Article  MathSciNet  MATH  Google Scholar 

  30. Turán, P.: Eine Extremalaufgabe aus der Graphentheorie. Mat. Fiz. Lapok 48, 436–452 (1941)

    MathSciNet  MATH  Google Scholar 

  31. Wood, D.R.: On the maximum number of cliques in a graph. Graphs Combin. 23(3), 337–352 (2007). https://doi.org/10.1007/s00373-007-0738-8

    Article  MathSciNet  MATH  Google Scholar 

  32. Zykov, A.A.: On some properties of linear complexes. Mat Sbornik N S 24(66), 163–188 (1949)

    MathSciNet  Google Scholar 

Download references

Funding

The first author is supported in part by the Simons Foundation under Grant no. 524435. The third author is supported in part by the Simons Foundation under Grant no. 429383.

Author information

Authors and Affiliations

  1. Montclair State University, Montclair, USA

    Jonathan Cutler

  2. University of Manitoba, Winnipeg, Canada

    JD Nir

  3. University of Nebraska-Lincoln, Lincoln, USA

    A. J. Radcliffe

Authors
  1. Jonathan Cutler
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. JD Nir
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. A. J. Radcliffe
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to JD Nir.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supported in part by the Simons Foundation under Grant no. 524435. Supported in part by the Simons Foundation under Grant no. 429383.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Cutler, J., Nir, J. & Radcliffe, A.J. Supersaturation for Subgraph Counts. Graphs and Combinatorics 38, 65 (2022). https://doi.org/10.1007/s00373-021-02454-y

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00373-021-02454-y

Keywords

Search

Navigation