Uniform Turán Density—Palette Classification
Random Structures & Algorithms · 2026-12 · 69 (4)
DOI: 10.1002/rsa.70106 ↗Kurz gefasst
Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 05.11.2026. Verfasst von Daniel Král' und 3 weiteren Autor:innen. Die Arbeit nennt 34 Literaturangaben. Gefördert von: European Research Council, National Science Foundation, Institute for Basic Science.
Abstract (Originalsprache)
In the 1980s, Erdős and Sós initiated the study of Turán hypergraph problems with a uniformity condition on the distribution of edges, that is, determining density thresholds for the existence of a hypergraph in a host hypergraph with edges uniformly distributed. In particular, Erdős and Sós asked to determine the uniform Turán densities of the hypergraphs and . After more than 30 years, the former was solved by Glebov, Král' and Volec [Israel J. Math. 211 (2016), 349–366] and Reiher, Rödl and Schacht [J. Eur. Math. Soc. 20 (2018), 1139–1159], while the latter still remains open. In these two cases and several additional cases, the tight lower bound is provided by a so‐called palette construction, that is, the existence of a palette that is not colorable with and that has the density equal to the uniform Turán density of . Lamaison [arXiv:2408.09643] has recently showed that the uniform Turán density of a 3‐uniform hypergraph is equal to the supremum of the densities of palettes that is not colorable with. We give a necessary and sufficient condition, which is easy to verify, on the existence of a 3‐uniform hypergraph colorable by each of palettes and not colorable by any palette . We also demonstrate how our result can be used to prove the existence of 3‐uniform hypergraphs with specific values of the uniform Turán density.
Förderung
- European Research Council
- National Science Foundation
- Institute for Basic Science
- National Research, Development and Innovation Office
Zitieren
APA
Král', D., Kučerák, F., Lamaison, A., & Tardos, G. (2026). Uniform Turán Density—Palette Classification. Random Structures & Algorithms, 69(4). https://doi.org/10.1002/rsa.70106
Vancouver
Král' D, Kučerák F, Lamaison A, Tardos G. Uniform Turán Density—Palette Classification. Random Structures & Algorithms. 2026;69(4). doi:10.1002/rsa.70106
BibTeX
@article{Krl2026,
author = {Král', Daniel and Kučerák, Filip and Lamaison, Ander and Tardos, Gábor},
title = {Uniform Turán Density—Palette Classification},
journal = {Random Structures & Algorithms},
year = {2026},
volume = {69},
number = {4},
doi = {10.1002/rsa.70106}
}
EUVIMED