Abstract
Denote by \({\mathcal {C}}^-_{\ell }\) the 3-uniform hypergraph obtained by removing one hyperedge from the tight cycle on \(\ell \) vertices. It is conjectured that the Turán density of \({\mathcal {C}}^-_{5}\) is 1/4. In this paper, we make progress toward this conjecture by proving that the Turán density of \({\mathcal {C}}^-_{\ell }\) is 1/4, for every sufficiently large \(\ell \) not divisible by 3. One of the main ingredients of our proof is a forbidden-subhypergraph characterization of the hypergraphs, for which there exists a tournament on the same vertex set such that every hyperedge is a cyclic triangle in this tournament. A byproduct of our method is a human-checkable proof for the upper bound on the maximum number of almost similar triangles in a planar point set, which was recently proved using the method of flag algebras by Balogh, Clemen, and Lidický.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Data availability
Not applicable.
Notes
When \({\varvec{{\mathcal {F}}}}= \{{\mathcal {F}}\}\), we use \(\textrm{ex}(n,{\mathcal {F}})\) and \(\pi ({\mathcal {F}})\) for \(\textrm{ex}(n,\{{\mathcal {F}}\})\) and \(\pi (\{{\mathcal {F}}\})\), respectively.
References
Aroskar, A., Cummings, J.: Limits, regularity and removal for finite structures. Preprint at arXiv:1412.8084 (2014)
Balogh, J., Clemen, F.C., Lidický, B.: Maximum number of almost similar triangles in the plane. Comput. Geom. 105/106, 15 (2022)
Bárány, I., Füredi, Z.: Almost similar configurations. Bull. Hellenic Math. Soc. 63, 17–37 (2019)
Choi, I., Lidický, B., Pfender, F.: Inducibility of directed paths. Discret. Math. 343(10), 112015 (2020)
Conway, J.H., Croft, H.T., Erdős, P., Guy, M.J.T.: On the distribution of values of angles determined by coplanar points. J. Lond. Math. Soc. (2) 19(1), 137–143 (1979)
Erdős, P.: On extremal problems of graphs and generalized graphs. Israel J. Math. 2, 183–190 (1964)
Erdős, P., Hajnal, A.: On Ramsey like theorems. Problems and results. In: Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972), pp. 123–140. Inst. Math. Appl., Southend-on-Sea (1972)
Erdős, P., Faudree, R., Pach, J., Spencer, J.: How to make a graph bipartite. J. Combin. Theory Ser. B 45(1), 86–98 (1988)
Falgas-Ravry, V., Pikhurko, O., Vaughan, E., Volec, J.: The codegree threshold of \(K^-_4\). J. Lond. Math. Soc. (2) 107(5), 1660–1691 (2023)
Glebov, R., Král’, D., Volec, J.: A problem of Erdős and Sós on 3-graphs. Israel J. Math. 211(1), 349–366 (2016)
Kamčev, N., Letzter, S., Pokrovskiy, A.: The Turán Density of Tight Cycles in Three-Uniform Hypergraphs. Int. Math. Res. Not. IMRN, rnad177 (2023)
Keevash, P.: Hypergraph Turán problems. In: Surveys in combinatorics 2011, Volume 392 of London Math. Soc. Lecture Note Ser., pp. 83–139. Cambridge Univ. Press, Cambridge (2011)
Kendall, M.G., Smith, B.B.: On the method of paired comparisons. Biometrika 31, 324–345 (1940)
Mantel, W.: Problem 28. In: Mantel, W. (ed.) Wiskundige Opgaven, pp. 60–61. Springer, New York (1907)
Mubayi, D., Pikhurko, O., Sudakov, B.: Hypergraph Turán problem: some open questions. In: AIM Workshop Problem Lists, p. 166 (2011)
Piga, S., Sales, M., Schülke, B.: The codegree Turán density of tight cycles minus one edge. Combin. Probab. Comput. 32(6), 881–884 (2023)
Razborov, A.A.: Flag algebras. J. Symb. Logic 72(4), 1239–1282 (2007)
Reiher, C., Rödl, V., Schacht, M.: On a generalisation of Mantel’s theorem to uniformly dense hypergraphs. Int. Math. Res. Not. 2018(16), 4899–4941 (2018)
Reiher, C., Rödl, V., Schacht, M.: On a Turán problem in weakly quasirandom 3-uniform hypergraphs. J. Eur. Math. Soc. 20(5), 1139–1159 (2018)
Acknowledgements
The authors are grateful to Bernard Lidický and Zoltán Füredi for helpful communication. They would also like to thank the anonymous referees for their helpful comments.
Funding
József Balogh: Research is partially supported by NSF Grants DMS-1764123, RTG DMS-1937241 and FRG DMS-2152488, the Arnold O. Beckman Research Award (UIUC Campus Research Board RB 22000), and the Langan Scholar Fund (UIUC). Haoran Luo: Research is partially supported by FRG DMS-2152488, the Arnold O. Beckman Research Award (UIUC Campus Research Board RB 22000).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Balogh, J., Luo, H. Turán Density of Long Tight Cycle Minus One Hyperedge. Combinatorica 44, 949–976 (2024). https://doi.org/10.1007/s00493-024-00099-y
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00493-024-00099-y