EUVIMEDEUVIMED entdecken
Crossref

Uniform Turán Density—Palette Classification

Daniel Král', Filip Kučerák, Ander Lamaison, Gábor Tardos

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →