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

A Turán Theorem for Extensions Via an Erdős-Ko-Rado Theorem for Lagrangians

  • Published:
Combinatorica Aims and scope Submit manuscript

Abstract

The extension of an r-uniform hypergraph G is obtained from it by adding for every pair of vertices of G, which is not covered by an edge in G, an extra edge containing this pair and (r−2) new vertices. In this paper we determine the Turán number of the extension of an r-graph consisting of two vertex-disjoint edges, settling a conjecture of Hefetz and Keevash, who previously determined this Turán number for r=3. As the key ingredient of the proof we show that the Lagrangian of intersecting r-graphs is maximized by principally intersecting r-graphs for r≥4.

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

Similar content being viewed by others

References

  1. R. Ahlswede and L. H. Khachatrian: The complete intersection theorem for systems of finite sets, European J. Combin.18 (1997), 125–136.

    Article  MathSciNet  Google Scholar 

  2. A. Brandt, D. Irwin and T. Jiang: Stability and Tur_an numbers of a class ofhypergraphs via Lagrangians, Combinatorics, Probability, and Computing2 (2017), 367–405.

    Article  Google Scholar 

  3. P. Frankl: The shifting technique in extremal set theory, Surveys in combinatorics1987 (New Cross, 1987), London Math. Soc. Lecture Note Ser., vol. 123, CambridgeUniv. Press, Cambridge, 1987, 81–110.

    MATH  Google Scholar 

  4. P. Frankl and V. Rődl: Hypergraphs do not jump, Journal of Symbolic Logic4(1984), 149–159.

    MathSciNet  MATH  Google Scholar 

  5. E. Friedgut: On the measure of intersecting families, uniqueness and stability, Combinatorica28 (2008), 503–528.

    Article  MathSciNet  Google Scholar 

  6. D. Hefetz and P. Keevash: A hypergraph Turán theorem via Lagrangians of intersecting families, J. Combin. Theory Ser. A120 (2013), 2020–2038.

    Article  MathSciNet  Google Scholar 

  7. Gy. Katona, T. Nemetz and M. Simonovits: On a problem of Turán in the theoryof graphs, Mat. Lapok15 (1964), 228–238.

    MathSciNet  MATH  Google Scholar 

  8. T. S. Motzkin and E. G. Straus: Maxima for graphs and a new proof of a theoremof Turán, Canad. J. Math. (1965), 533–540.

    Google Scholar 

  9. S. Norin and L. Yepremyan: On Turán numbers of extensions, arXiv:1510.04689, 2015.

    MATH  Google Scholar 

  10. S. Norin and L. Yepremyan: Turán number of generalized triangles, J. Combin.Theory Ser. A146 (2017), 312–343.

    Article  MathSciNet  Google Scholar 

  11. O. Pikhurko: Exact computation of the hypergraph Turán function for expandedcomplete 2-graphs, J. Combin. Theory Ser. B103 (2013), 220–225.

    Article  MathSciNet  Google Scholar 

  12. A. F. Sidorenko: The maximal number of edges in a homogeneous hypergraphcontaining no prohibited subgraphs, Mathematical notes of the Academy of Sciencesof the USSR41 (1987), 247–259.

    Article  Google Scholar 

  13. B. Wu, Y. Peng and P. Chen: On a conjecture of Hefetz and Keevash on lagrangiansof intersecting hypergraphs and Turán numbers, arXiv:1701.06126, 2017.

    Google Scholar 

  14. L. Yepremyan: Local stability method for hypergraph Turán problems, Ph.D. thesis, McGill University, 2016.

    Google Scholar 

Download references

Acknowledgement

Some of this research was performed in Summer 2015, when the first author was an undergraduate student at McGill University supported by an NSERC USRA scholarship.

Author information

Authors and Affiliations

  1. Physics Department, MIT, Cambridge, MA, 02142, USA

    Adam Bene Watts

  2. Department of Mathematics and Statistics, McGill University, Montreal, Canada

    Sergey Norin

  3. Mathematical Institute, University of Oxford, Oxford, OX2 6GG, UK

    Liana Yepremyan

Authors
  1. Adam Bene Watts
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sergey Norin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Liana Yepremyan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Liana Yepremyan.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Watts, A.B., Norin, S. & Yepremyan, L. A Turán Theorem for Extensions Via an Erdős-Ko-Rado Theorem for Lagrangians. Combinatorica 39, 1149–1171 (2019). https://doi.org/10.1007/s00493-019-3831-8

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00493-019-3831-8

Mathematics Subject Classification (2010)

Search

Navigation