The Turán Number of Surfaces

EUROCOMB’23

Abstract
We show that there is a constant $c$ such that any 3-uniform hypergraph ${\mathcal H}$ with $n$ vertices and at least $cn^{5/2}$ edges contains a triangulation of the real projective plane as a sub-hypergraph. This resolves a conjecture of Kupavskii, Polyanskii, Tomon, and Zakharov. Furthermore, our work, combined with prior results, asymptotically determines the Turán number of all surfaces.

Pages:
799–805
References

Füredi, Zoltán, and Miklós Simonovits. 2013. "The History of Degenerate (Bipartite) Extremal Graph Problems." In Erdős Centennial, 25:169-264. Bolyai Soc. Math. Stud. János Bolyai Math. Soc., Budapest. https://doi.org/10.1007/978-3-642-39286-3_7.
https://doi.org/10.1007/978-3-642-39286-3

Georgakopoulos, Agelos, John Haslegrave, Richard Montgomery, and Bhargav Narayanan. 2022. "Spanning Surfaces in 3-Graphs." J. Eur. Math. Soc. 24 (1): 303-39. https://doi.org/10.4171/jems/1101.
https://doi.org/10.4171/JEMS/1101

Keevash, Peter. 2011. "Hypergraph Turán Problems." In Surveys in Combinatorics 2011, 392:83-139. London Math. Soc. Lecture Note Ser. Cambridge Univ. Press, Cambridge. https://mathscinet-ams-org.stanford.idm.oclc.org/mathscinet-getitem?mr=2866732.
https://doi.org/10.1017/CBO9781139004114.004

Keevash, Peter, Jason Long, Bhargav Narayanan, and Alex Scott. 2021. "A Universal Exponent for Homeomorphs." Israel J. Math. 243 (1): 141-54. https://doi.org/10.1007/s11856-021-2156-7.
https://doi.org/10.1007/s11856-021-2156-7

Kupavskii, Andrey, Alexandr Polyanskii, István Tomon, and Dmitriy Zakharov. n.d. "The Extremal Number of Surfaces." Int. Math. Res. Not. 2022: 13246-71. https://doi.org/10.1093/imrn/rnab099.
https://doi.org/10.1093/imrn/rnab099

Linial, Nati. 2008. "What Is High-Dimensional Combinatorics?" In. Random-Approx.

Linial, Nati. 2018. "Challenges of High-Dimensional Combinatorics." In. Lovász's Seventieth Birthday Conference.

Luria, Zur, and Ran J. Tessler. 2019. "A Sharp Threshold for Spanning 2-Spheres in Random 2-Complexes." Proc. Lond. Math. Soc. 119 (3): 733-80. https://doi.org/10.1112/plms.12247.
https://doi.org/10.1112/plms.12247

Mubayi, Dhruv, Oleg Pikhurko, and Benny Sudakov. 2011. "Hypergraph Turán Problem: Some Open Questions." In AIM Workshop Problem Lists, Manuscript.

Sankar, Maya. 2022. "The Turán Number of Surfaces." Preprint available at https://arxiv.org/abs/2210.11041.

Sós, V. T., P. Erdős, and W. G. Brown. 1973. "On the Existence of Triangulated Spheres in -Graphs, and Related Problems." Period. Math. Hungar. 3 (3-4): 221-28. https://doi.org/10.1007/BF02018585.
https://doi.org/10.1007/BF02018585

Metrics

0

Views

0

PDF views