Uniform Tur\'an density beyond 3-graphs

Ander Lamaison

REVIEW 1 major objections 5 minor 22 references

Uniform Tur\'an density beyond 3-graphs

T0 review · 1 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For every $r\ge 3$, there are $r$-uniform hypergraphs with uniform Tur\'an density exactly $1/4$ and exactly $\binom{r}{2}^{-\binom{r}{2}}$.

desk verdict The first non-zero uniform Turán densities for every r≥5 are here, with a real but repairable gap in Lemma 15. read the letter →

arxiv 2508.20696 v1 pith:ZRXDWXBA submitted 2025-08-28 math.CO

Ander Lamaison This is my paper · ORCID

classification math.CO MSC 05C6505C3505D1005D40

keywords uniformTurandensityhypergraphsquasi-lineardescriptivesequencesreducedhypergraphregularitylemmaextremalcombinatoricsRamseytheory

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes the first explicit values of the uniform Tur\'an density---the density threshold above which every large-enough locally dense $r$-uniform hypergraph is forced to contain a copy of a given pattern $F$---for all uniformities $r\ge 3$. It proves that for every $r$, some $r$-graph has uniform Tur\'an density exactly $1/4$ and some $r$-graph has uniform Tur\'an density exactly $\binom{r}{2}^{-\binom{r}{2}}$. Before this work, no non-zero uniform Tur\'an density was known for any $r\ge 5$, so the set of attainable values was effectively unexplored outside 3-graphs. The proof isolates a structural class of hypergraphs (quasi-linear hypergraphs with controlled twin-pair intersections) and shows that two prescribed descriptive sequences force the density to take these two values exactly.

What carries the argument

The machinery that carries the argument is the quasi-linear hypergraph, an $r$-graph in which every edge has a unique twin edge sharing exactly two vertices while all other edge intersections have size at most one, together with descriptive sequences: strings of $2r-2$ letters $X,Y,Z$ (with $r-2$ of each of $X$ and $Y$, and two $Z$'s) that record the order in which the vertices of a twin pair appear. A twin pair described by $XX\ldots XZZYY\ldots Y$ is one in which the head (first two vertices) of one edge is the tail (last two vertices) of the other, and head-tail-mixing means every vertex order contains such a coincidence; the inconsistent sequences are those in which the shared pair plays different numeric roles inside the two edges. The density theorems are proved by passing through reduced hypergraphs, auxiliary graphs formed from the second layer of the regularity partition, and using two Ramsey-type lemmas (Lemmas 14 and 15) that force large sets of indices in which every relevant tuple admits the required descriptive sequence. The hypergraph regularity lemma and counting lemma then upgrade that combinatorial certificate to an actual subgraph copy in the original dense hypergraph.

What would settle it

For $r=4$ and $\varepsilon=0.01$, searching for a reduced hypergraph of density $0.26$ whose large index sets all miss the sequence $XX\ldots XZZYY\ldots Y$ would test Lemma 14; finding one would refute the $1/4$ upper bound.

Watch

Extended reading notes

Core claim

The central assertion is that exact uniform Tur\'an density is governed by the relative order of vertices in twin pairs of edges. For every $r\ge 3$, every quasi-linear, head-tail-mixing $r$-graph $F$ that admits the descriptive sequence $XX\ldots XZZYY\ldots Y$ has $\pi_u(F)=1/4$, and every quasi-linear, inconsistent $r$-graph $F$ that admits all inconsistent descriptive sequences of order $r$ has $\pi_u(F)=\binom{r}{2}^{-\binom{r}{2}}$. Such hypergraphs are shown to exist for every $r$, so the values $1/4$ and $\pi_r$ are genuine uniform Tur\'an densities in every uniformity. The lower bounds come from explicit random pair-coloring constructions producing locally dense $F$-free hypergraphs; the upper bounds use the hypergraph regularity lemma and counting lemma to show that any locally $(d+\varepsilon)$-dense hypergraph must contain $F$.

Load-bearing premise

The upper-bound proofs assume that the cited hypergraph regularity and counting lemmas work with the exact chain of smallness conditions chosen in Section 7; if those lemmas fail at that level of precision, the claim that every sufficiently dense locally dense hypergraph contains $F$ collapses.

Editorial extensions

If this is right

For every $r\ge 3$ the value $1/4$ occurs as a uniform Tur\'an density, giving the first explicit non-zero values for $r\ge 5$.
The value $\binom{r}{2}^{-\binom{r}{2}}$ is attained for every $r$; if the paper's Conjecture 20 is correct, this number is the minimum positive uniform Tur\'an density for $r$-graphs.
All $r$-graphs in the head-tail-mixing class described by $XX\ldots XZZYY\ldots Y$ are density-forcing at $1/4$: every locally $(1/4+\varepsilon)$-dense $r$-graph contains every such $F$.
The lower-bound constructions are simple random palettes, so the extremal examples are cheap to describe and essentially explicit.
The two results unify previously separate 3-graph and 4-graph statements into a single uniformity-independent theorem.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If Conjecture 20 is true, Theorem 3 implies that the set of positive uniform Tur\'an densities has a jump at exactly $\pi_r$ for every $r$, matching the known 3-graph jump at $1/27$.
The Section 8 counterexample to the palette-blowup lemma for 4-graphs suggests that a full palette characterization of uniform Tur\'an density may be impossible for $r\ge 4$; the descriptive-sequence method here bypasses that obstruction, so a promising next step is to ask whether the theorems extend to hypergraphs with larger edge intersections.
The existence proof for the inconsistent case builds hypergraphs on multidimensional grids via lexicographic Ramsey theory; this hints that explicit extremal hypergraphs for $\pi_r$ may be constructible with far fewer vertices than the nowhere-empty random construction suggests.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick take: this is the paper that finally gets uniform Turán density off zero for r-graphs with r≥5. For every r≥3 it gives quasi-linear r-graphs with π_u=1/4 and with π_u=binom(r,2)^{-binom(r,2)}; for r≥5 neither value was previously known, and the π_r value matches the conjectured minimum positive value, so this is a genuine landmark.

The lower bounds are clean and fully proved: palettes—random colorings of pairs—that are locally d-dense and F-free by construction, with no parameter fitting. The upper-bound strategy is the right generalization of Reiher's reduced hypergraph method: build a (k,r)-reduced graph from the second layer of the regularity partition, find a large index set whose 2r-2-tuples all admit the right descriptive sequence, then use the counting lemma with the sequence as a template. The parameter hierarchy is heavy, but I did not see any hidden circularity; the self-citations are to the r=3 base cases and the palette theorem, and the r≥4 arguments stand on their own.

The soft spot is real and it is in Lemma 15. As printed, the proof drops a factor q. The profile entry a_{i,j} is floor(q|V∩W|/|V|), so the correct consequence is |W_{i,j}| ≥ (a_{i,j}/q)|V_{a,b}|, not |W_{i,j}| ≥ a_{i,j}|V_{a,b}|. To force an intersection you then need Σa_{i,j} > q, and the AM-GM line only gives Σa > 1. The same proof also loses q when passing from c(q(∏(a+1)/q)^{1/c}-1) to c((π_r+ε)^{1/c}-1/q). The slips roughly cancel in the direction of being too weak. I checked the intended fix: with c=binom(r,2) and q=ceil(2^c/ε), the corrected lower bound is Σa ≥ q(1+ε/π_r)^{1/c}-c, which is comfortably bigger than q. So this is repairable, but as written Lemma 15 is not proved, and Lemma 15 is the sole source of the inconsistent descriptive sequence in the upper bound for Theorem 11. A referee has to ask for this to be rewritten.

Smaller point: the concluding example of a (k,4)-reduced graph with no positive-density palette blowup is asserted with a one-line sketch. It is not needed for the main theorems, but if it stays in the paper it needs a proof.

Verdict: important, technically serious, and publishable after the Lemma 15 fix. I would send it to a top combinatorics journal and ask for a careful revision; I would not desk reject.

Referee Report

1 major / 5 minor

Summary. This paper studies the uniform Turán density π_u(F) of r-uniform hypergraphs. The main results are Theorem 2 and Theorem 3, asserting that for every r≥3 there exists an r-graph F with π_u(F)=1/4 and an r-graph F with π_u(F)=binom(r,2)^{-binom(r,2)}. These are derived from two structural theorems: Theorem 10 identifies a class of quasi-linear, head-tail-mixing r-graphs with π_u=1/4, and Theorem 11 identifies a class of quasi-linear, inconsistent r-graphs with π_u=π_r. The existence of such hypergraphs is established in Theorems 12 and 13 via explicit constructions from nowhere-empty linear hypergraphs. The upper-bound proofs use the hypergraph regularity lemma and the associated counting lemma, applied through auxiliary reduced hypergraphs. The paper concludes with a conjecture on the minimum positive value of π_u and a discussion of the limitations of palette characterizations for r≥4.

Significance. The paper is significant: it provides the first explicit values of the uniform Turán density for all uniformities r≥4, giving two distinct values (1/4 and binom(r,2)^{-binom(r,2)}) for every r. The lower-bound constructions in Theorems 12 and 13 are concrete and fully verified, and the paper does not rely on fitting parameters to a predetermined answer. The conceptual framework (quasi-linear hypergraphs, descriptive sequences, head-tail mixing) is natural and likely to be reused. The conjectures on the minimum positive value and on the zero-density characterization are well posed, and the counterexample to the palette approach for r=4 is a valuable caution. However, because the upper-bound proof of Theorem 11 rests on Lemma 15, whose printed proof contains a scaling error, the full set of claims is conditional on a repair of that lemma.

major comments (1)

[Section 5, Lemma 15] The proof of Lemma 15 as printed contains a scaling error that invalidates the contradiction argument. From the definition a_{i,j} = floor(q |V_{t_i,t_j} ∩ W| / |V_{t_i,t_j}|), the correct lower bound for the set W_{i,j} ⊆ V_{a,b} is |W_{i,j}| ≥ (a_{i,j}/q)|V_{a,b}|, not |W_{i,j}| ≥ a_{i,j}|V_{a,b}| as claimed in the paragraph 'Let W_{i,j} be the set...'. Therefore the intersection argument requires Σ a_{i,j} > q, not Σ a_{i,j} > 1. The displayed AM-GM chain concludes with a bound equivalent to Σ a_{i,j} > 1: the factor q is dropped in passing from C(q∏((a_{i,j}+1)/q)^{1/C} − 1) to C((π_r+ε)^{1/C} − 1/q). The contradiction in Lemma 15 is thus not justified. This is load-bearing because Lemma 15 is the only source of the inconsistent descriptive sequence σ used in Step 5 of the upper-bound proof of Theorem 11, and hence for the claimed exact value π_u(F) = π_r for r≥4. The gap appears repairable: with C = binom(r,2) and q = ceil(2^C/ε), the corrected AM-GM lower bound Σ a ≥ C(q(π_r+ε)^{1/C} − 1) = q(1+ε/π_r)^{1/C} − C exceeds q, so restoring the missing factor q would justify the intersection argument. The proof should be rewritten accordingly.

minor comments (5)

[Section 7.3] In the definition of the lower-bound construction for Theorem 11, the condition 'for all 1≤i<j≤n' should read 'for all 1≤i<j≤r'.
[Section 7.2] The definition of μ as '4rr/ε' should be '4r^r/ε'.
[Section 7.3] The sentence 'we can finish as in the proof of Theorem 10' would benefit from an explicit note that the two Z entries of the descriptive sequence σ play the same role as the head-tail pair in Theorem 10, so the well-definedness of the functions f_i carries over without change.
[Throughout] There are a number of typographical errors, including 'tehnique' (Section 1), 'desctiptive' (Section 4), 'important role important role' (Section 3), and the unneeded comma at the end of Theorem 12. These should be corrected.
[Section 5, Lemma 15] The expressions 'q3' and '32r−2+1' should be 'q^3' and '3^{2r-2}+1'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the main theorems are derived from explicit constructions and external regularity lemmas.

full rationale

The derivation chain is not circular. Theorems 2 and 3 are split into conditional density theorems (Theorems 10 and 11) and existence constructions (Theorems 12 and 13). The lower bounds are explicit random palette constructions: Theorem 10 colors pairs red/blue and keeps r-tuples whose head pair is red and tail pair is blue, giving density 1/4; Theorem 11 colors pairs with the elements of [r]-choose-2 and keeps the unique admissible pattern, giving density pi_r. No parameter is fitted to the target constant. The upper bounds are supersaturation arguments that use the externally cited hypergraph regularity and counting lemmas of Rodl and Schacht (Theorems 17 and 18); after cleaning the partition, the proof builds a dense reduced hypergraph, applies Lemma 14 or 15 to obtain a descriptive sequence, and then uses the counting lemma to embed F. The self-citations to the author's earlier work are historical or programmatic. In particular, [11] is explicitly stated to fail for r>=4, so it is not load-bearing in the new results. No definition or equation is equivalent to the claimed conclusion by construction; the possible algebraic slip in Lemma 15 noted in the skeptical review is a correctness concern, not a circularity concern. Thus the paper receives score 0 for circularity.

Assumptions & free parameters 0 free parameters · 7 assumptions · 3 invented entities

The central claims depend on standard heavy results in extremal combinatorics: the hypergraph regularity lemma, the counting lemma, Ramsey-type theorems, and packing results. No parameters are fitted to data. The new definitions, quasi-linear hypergraphs, descriptive sequences, and head-tail-mixing, are explicit combinatorial objects whose relevant properties are proved within the paper, so they are not unexplained postulates.

assumptions (7)

standard math Hypergraph regularity lemma (Theorem 17, cited from Rödl and Schacht [21])
Used in Step 1 of the upper bound proofs of Theorems 10 and 11 to obtain a regular nested partition with the stated hierarchical parameters.
standard math Hypergraph counting lemma (Theorem 18, cited from Rödl and Schacht [20])
Used in Step 6 to embed a copy of F into H once the reduced graph structure and descriptive sequence are found.
standard math Ramsey's theorem (Theorem 4)
Used to find monochromatic cliques in edge colorings of complete hypergraphs in the reduced graph arguments in Lemmas 14 and 15 and in Step 3.
standard math Fishburn-Graham lexicographic Ramsey theorem (Lemma 6)
Used in the proof of Theorem 13 to find product sets S1×...×Sd sorted by layers under an arbitrary vertex ordering.
standard math Rödl's packing theorem [18]
Used in the lower bound density arguments to find large families of r-tuples pairwise intersecting in at most one vertex.
standard math Chernoff bound and standard concentration inequalities
Used to show that the palette-generated hypergraphs are locally dense with high probability.
domain assumption Standard definitional framework of uniform Turán density and local density (Definition 1)
The paper adopts the standard definition introduced by Erdős and Sós; all results are stated within this framework.

invented entities (3)

Quasi-linear r-graphs
purpose: A class of hypergraphs where each edge has a unique twin intersecting in exactly two vertices and all other intersections are at most one; used to isolate the combinatorial structure that yields the target densities.
Introduced in Section 3. It is fully defined and its properties are proved; it is not an unexplained postulate.
Descriptive sequences and consistent/inconsistent hypergraphs
purpose: Encode the relative order of vertices in twin edge pairs; consistency determines whether a palette construction can avoid a given F.
Introduced in Section 3 and used to state Theorems 10 and 11. These are combinatorial bookkeeping devices with proven structural roles.
Head-tail-mixing hypergraphs
purpose: A property of vertex orderings that forces a 1/4-density palette construction to avoid F.
Defined in Section 3; the property is used to prove π_u(F)=1/4 for the constructed family.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Uniform Tur\'an density beyond 3-graphs." pith.science (2026). https://pith.science/paper/ZRXDWXBA

@misc{pith2026250820696,
  author       = {Pith},
  title        = {Pith review of: Uniform Tur\'an density beyond 3-graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZRXDWXBA}},
  note         = {Machine review of arXiv:2508.20696}
}

abstract

In the 1980s, Erd\H{o}s and S\'os first introduced an extremal problem on hypergraphs with density constraints. Given an $r$-uniform hypergraph $F$ (or $r$-graph for short), its uniform Tur\'an density $\pi_u(F)$ is the smallest value of $d$ in which every hypergraph $H$ in which every linear-sized subhypergraph of $H$ has edge density at least $d$ contains $F$ as a subgraph. The first non-zero value of $\pi_u(F)$ was not found until 30 years later. Progress in studying the set of values of the uniform Tur\'an density of $r$-graphs has been uneven in terms of $r$: to this day there are infinitely many non-zero values known for $r=3$, a single non-zero value known for $r=4$ and none for $r\geq 5$. In this paper we obtain the first explicit values of $\pi_u$ for all uniformities, by proving that for every $r\geq 3$ there exist $r$-graphs $F$ with $\pi_u(F)=1/4$ and with $\pi_u(F)=\binom{r}{2}^{-\binom{r}{2}}$.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 20 canonical work pages

[1]

B´ ar´ any and P

I. B´ ar´ any and P. Valtr. A positive fraction Erd˝ os-Szekeres theorem.Discrete and Computational Geometry , 19:335–342, 1998

work page 1998
[2]

Buci´ c, J

M. Buci´ c, J. W. Cooper, D. Kr´ al’, S. Mohr, and D. Munh´ a Correia. Uniform tur´ an density of cycles.Transactions of the American Mathematical Society, 376(7):4765–4809, 2023

work page 2023
[3]

Erd˝ os and A

P. Erd˝ os and A. Hajnal. On Ramsey like theorems. Problems and results. Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst.,) , pages 123– 140, 1972

work page 1972
[4]

Erd˝ os and V

P. Erd˝ os and V. T. S´ os. On Ramsey-Tur´ an type theorems for hypergraphs. Combinatorica, 2(3):289–295, 1982

work page 1982
[5]

Erd˝ os and A

P. Erd˝ os and A. H. Stone. On the structure of linear graphs. Bulletin of the American Mathematical Society, 52(12):1087–1091, 1946. 26

work page 1946
[6]

P. C. Fishburn and R. L. Graham. Lexicographic ramsey theory. Journal of Combinatorial Theory, Series A , 62:280–298, 1993

work page 1993
[7]

Garbe, D

F. Garbe, D. Kr´ al’, and A. Lamaison. Hypergraphs with minimum positive uniform Tur´ an density.Israel Journal of Mathematics, 259(2):701–726, 2024

work page 2024
[8]

Glebov, J

R. Glebov, J. Volec, and D. Kr´ al’. A problem of Erd˝ os and S´ os on 3-graphs. Israel Journal of Mathematics , 211(1):349–366, 2016

work page 2016

Show all 22 references

[9]

Gunderson and J

K. Gunderson and J. Semeraro. Tournaments, 4-uniform hypergraphs, and an exact extremal result. Journal of Combinatorial Theory, Series B , 126:114–136, 2017

2017
[10]

Kohayakawa, B

Y. Kohayakawa, B. Nagle, V. R¨ odl, and M. Schacht. Weak hypergraph regularity and linear hypergraphs. J. Combin. Theory Ser. B , 100:151–160, 2010

2010
[11]

Lamaison

A. Lamaison. Palettes determine uniform Tur´ an density. Preprint. arXiv:2408.09643, 2024

2024 arXiv
[12]

Lamaison and Z

A. Lamaison and Z. Wu. The uniform Tur´ an density of large stars. Preprint. arXiv:2409.03699, 2024

2024 arXiv
[13]

H. Lin, G. Wang, and W. Zhou. The minimum positive uniform Tur´ an den- sity in uniformly dense k-uniform hypergraphs. Preprint. arXiv:2305.01305, 2023

2023 arXiv
[14]

F. P. Ramsey. On a problem of formal logic. Proceedings of the London Mathematical Society, 2(1):264–286, 1930

1930
[15]

C. Reiher. Extremal problems in uniformly dense hypergraphs. European Journal of Combinatorics , 88:103117, 2020

2020
[16]

Reiher, V

C. Reiher, V. R¨ odl, and M. Schacht. Hypergraphs with vanishing Tur´ an density in uniformly dense hypergraphs.Journal of the London Mathematical Society, 97(1):77–97, 2018

2018
[17]

Reiher, V

C. Reiher, V. R¨ odl, and M. Schacht. On a generalisation of Mantel’s the- orem to uniformly dense hypergraphs. International Mathematics Research Notices, 16:4899–4941, 2018

2018
[18]

V. R¨ odl. On a packing and covering problem. European Journal of Combi- natorics, 6:69–78, 1985

1985
[19]

V. R¨ odl. On universality of graphs with uniformly distributed edges.Discrete Mathematics, 59(1-2):125–134, 1986. 27

1986
[20]

R¨ odl and M

V. R¨ odl and M. Schacht. Regular partitions of hypergraphs: counting lem- mas. Combinatorics, Probability and Computing , 16(6):887–901, 2007

2007
[21]

R¨ odl and M

V. R¨ odl and M. Schacht. Regular partitions of hypergraphs: regularity lemmas. Combinatorics, Probability and Computing , 16(6):833–885, 2007

2007
[22]

P. Tur´ an. Research problems.Magyar Tud. Akad. Mat. Int. K¨ ozl, 6:417–423, 1961. 28

1961

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [1]

B´ ar´ any and P

I. B´ ar´ any and P. Valtr. A positive fraction Erd˝ os-Szekeres theorem.Discrete and Computational Geometry , 19:335–342, 1998

work page 1998

[2] [2]

Buci´ c, J

M. Buci´ c, J. W. Cooper, D. Kr´ al’, S. Mohr, and D. Munh´ a Correia. Uniform tur´ an density of cycles.Transactions of the American Mathematical Society, 376(7):4765–4809, 2023

work page 2023

[3] [3]

Erd˝ os and A

P. Erd˝ os and A. Hajnal. On Ramsey like theorems. Problems and results. Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst.,) , pages 123– 140, 1972

work page 1972

[4] [4]

Erd˝ os and V

P. Erd˝ os and V. T. S´ os. On Ramsey-Tur´ an type theorems for hypergraphs. Combinatorica, 2(3):289–295, 1982

work page 1982

[5] [5]

Erd˝ os and A

P. Erd˝ os and A. H. Stone. On the structure of linear graphs. Bulletin of the American Mathematical Society, 52(12):1087–1091, 1946. 26

work page 1946

[6] [6]

P. C. Fishburn and R. L. Graham. Lexicographic ramsey theory. Journal of Combinatorial Theory, Series A , 62:280–298, 1993

work page 1993

[7] [7]

Garbe, D

F. Garbe, D. Kr´ al’, and A. Lamaison. Hypergraphs with minimum positive uniform Tur´ an density.Israel Journal of Mathematics, 259(2):701–726, 2024

work page 2024

[8] [8]

Glebov, J

R. Glebov, J. Volec, and D. Kr´ al’. A problem of Erd˝ os and S´ os on 3-graphs. Israel Journal of Mathematics , 211(1):349–366, 2016

work page 2016