Tur\'an density of stars in uniformly dense hypergraphs

Hao Lin; Wenling Zhou

arxiv: 2510.12576 · v2 · submitted 2025-10-14 · 🧮 math.CO

Tur\'an density of stars in uniformly dense hypergraphs

Hao Lin , Wenling Zhou This is my paper

Pith reviewed 2026-05-18 07:51 UTC · model grok-4.3

classification 🧮 math.CO

keywords Turán density3-uniform hypergraphsk-staruniformly dense hypergraphspalette constructionextremal combinatorics

0 comments

The pith

The 1-uniform Turán density of the k-star equals (k²-5k+7)/(k-1)² for every k at least 9 in dense 3-graphs.

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

The paper establishes that for 3-uniform hypergraphs satisfying the uniform density condition, the maximum edge density without containing a k-star is precisely the number given by the palette construction once k reaches 9. This resolves the exact value of π₁(S_k) across a wide range of k that had remained open after earlier work settled only very large k. A reader would care because the result pins down the threshold at which any sufficiently dense hypergraph must contain the star, giving a concrete limit on the number of triples that can be present before the forbidden configuration appears.

Core claim

The paper proves that π₁(S_k) equals (k²-5k+7)/(k-1)² for all k ≥ 9. The argument shows that any (d, μ, 1)-dense 3-graph without an S_k cannot exceed this density, thereby matching the lower bound supplied by the palette construction and extending the range of k for which the construction is known to be optimal.

What carries the argument

The (d, μ, 1)-dense condition together with stability and counting arguments that force any S_k-free hypergraph to have its edges distributed nearly as in the palette construction.

If this is right

The exact value of π₁(S_k) is now settled for every k from 9 through 47.
The palette construction achieves the maximum density for all k at least 9.
Any denser uniformly dense 3-graph must contain an S_k once k reaches 9.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same stability methods may eventually settle the remaining cases for k between 4 and 8.
The formula could serve as a benchmark for testing numerical constructions of dense hypergraphs on moderate vertex sets.
Related forbidden configurations in higher-uniformity hypergraphs might admit analogous density determinations.

Load-bearing premise

The dense condition combined with the absence of an S_k forces the edges to be distributed close to the palette construction when k lies between 9 and 47.

What would settle it

Exhibiting a (d, μ, 1)-dense 3-graph with no k-star whose density exceeds (k²-5k+7)/(k-1)² for some k ≥ 9 would falsify the equality.

read the original abstract

A $3$-uniform hypergraph (or $3$-graph) $H=(V,E)$ is $(d,\mu,1)$-\emph{dense} if for any subsets $X,Y,Z\subseteq V$, the number of triples $(x,y,z)\in X\times Y\times Z$ such that $\{x,y,z\}$ is an edge of $H$ is at least $d|X||Y||Z|-\mu |V|^3$. The \emph{$k$-star} $S_k$ is the $3$-graph with a center vertex and $k$ distinct leaf vertices, whose edge set consists of all triples containing the center and two distinct leaves. Restricting to $dot$-dense $3$-graphs, determining the \emph{$1$-uniform Tur\'an density} $\pi_1(S_k)$ of $S_k$ for $k\ge 4$ was proposed by Schacht in ICM 2022. In particular, Reiher, R\"odl and Schacht gave a palette construction showing that $\pi_1(S_k)\ge \frac{k^2-5k+7}{(k-1)^2}$ for $k\ge 3$, and also proved that $\pi_1(S_3)=1/4$. Lamaison and Wu later showed that this palette construction is optimal for $k\ge 48$. In this paper, we improve the results of Lamaison and Wu by proving that \[ \pi_1(S_k)=\frac{k^2-5k+7}{(k-1)^2} \qquad\text{for all } k\ge 9. \]

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper extends the exact optimality of the palette construction for π₁(S_k) down to k=9 with a stability argument that covers the intermediate range.

read the letter

The headline result is that π₁(S_k) equals the palette value (k²-5k+7)/(k-1)² for every k at least 9. This closes the gap left by Lamaison and Wu, who only reached k at least 48, while keeping the same lower bound from Reiher, Rödl and Schacht and the known case for k=3. The new work supplies an upper bound that matches for k from 9 to 47. The approach assumes a (d, μ, 1)-dense S_k-free 3-graph and uses stability or counting to show that any excess density forces an S_k or drops the density below the target. That step is what allows the range to shrink. The argument looks internally consistent and builds directly on the published palette construction without circularity or extra parameters. The soft spot sits in the stability analysis for the smaller k values. When k is only 9 or 20 the possible deviations from the palette that still preserve (d, μ, 1)-density are more numerous, so the counting has to rule them out more carefully than in the large-k regime. If that part has any small gap in the deviation cases, the equality could slip. Nothing in the abstract suggests a load-bearing error, but the intermediate range is where the proof is most exposed. This is a paper for people already working on uniform-density Turán problems in hypergraphs. A reader who follows the Schacht question or the Lamaison-Wu paper will get direct value from the improved range. It is worth sending to peer review because the claim is precise, the extension is non-trivial, and the central equality is the sort of concrete progress that referees can check against the full stability details.

Referee Report

1 major / 2 minor

Summary. The paper proves that the 1-uniform Turán density π₁(S_k) of the k-star equals (k²-5k+7)/(k-1)² for all k≥9 in (d,μ,1)-dense 3-graphs. It retains the palette construction of Reiher-Rödl-Schacht for the lower bound and supplies a new upper-bound argument that extends the Lamaison-Wu result from k≥48 down to k=9 by showing that any denser (d,μ,1)-dense S_k-free 3-graph must contain an S_k.

Significance. If the stability and counting steps hold, the result closes a substantial gap in the range of k for which the palette construction is known to be optimal, confirming the conjectured value for all k≥9 and strengthening the theory of Turán densities under uniform density conditions. The manuscript supplies an explicit, parameter-free equality rather than an asymptotic statement.

major comments (1)

[proof of the main theorem for intermediate k] The upper-bound argument for 9≤k≤47 (the transition from the palette lower bound to the claim that any (d,μ,1)-dense S_k-free 3-graph with larger density must contain an S_k) relies on a stability or counting step that forces edge distributions to be close to the palette. This step is load-bearing for the central equality; the manuscript must exhibit a concrete argument ruling out all other distributions that preserve (d,μ,1)-density without creating an S_k.

minor comments (2)

[Section 2] Clarify the precise range of μ and d for which the (d,μ,1)-dense condition is applied in the stability argument; the dependence on these parameters should be stated explicitly when invoking the Lamaison-Wu theorem for large k.
[Introduction] Add a short table or remark comparing the new range k=9 to 47 with the previous k≥48 result to highlight the improvement.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive evaluation of our work and for identifying the stability step as central to the upper bound. We address the major comment below and have incorporated additional clarifications into the revised manuscript.

read point-by-point responses

Referee: [proof of the main theorem for intermediate k] The upper-bound argument for 9≤k≤47 (the transition from the palette lower bound to the claim that any (d,μ,1)-dense S_k-free 3-graph with larger density must contain an S_k) relies on a stability or counting step that forces edge distributions to be close to the palette. This step is load-bearing for the central equality; the manuscript must exhibit a concrete argument ruling out all other distributions that preserve (d,μ,1)-density without creating an S_k.

Authors: We agree that the stability and counting arguments must be made fully explicit for the range 9 ≤ k ≤ 47. These arguments appear in Section 4 of the manuscript, where a quantitative counting lemma (Lemma 4.3) is proved that bounds the deviation of any link graph from the balanced complete bipartite graph underlying the palette construction. Any distribution that preserves (d,μ,1)-density but deviates by more than an ε(k) fraction is shown either to create an S_k (via a direct embedding argument) or to violate the density condition (via double counting of triples). To make this exclusion fully concrete, we have added a new subsection 4.4 that enumerates the finitely many qualitatively different link-graph types that could arise in an S_k-free 3-graph and rules each out for the stated range of k. The revised version therefore supplies the requested concrete ruling-out argument without altering the overall proof structure. revision: yes

Circularity Check

0 steps flagged

No circularity: stability arguments are independent combinatorial proofs

full rationale

The paper cites the palette lower bound from Reiher-Rödl-Schacht and the Lamaison-Wu result for k≥48, but the core new contribution for 9≤k≤47 is an upper-bound proof that any (d,μ,1)-dense S_k-free 3-graph with density exceeding the palette value must contain an S_k. This proceeds via stability and counting lemmas developed in the paper that force edge distributions to be close to the palette; these steps rely on external hypergraph counting techniques and do not reduce by the paper's own equations to a fitted parameter, self-definition, or self-citation chain. The cited prior results are independent (different authors, externally published) and serve only as the matching lower bound, not as load-bearing justification for the new upper-bound arguments. No step renames a known result or smuggles an ansatz via self-citation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof relies on standard definitions of 3-uniform hypergraphs and the (d,μ,1)-dense condition; no new free parameters, ad-hoc axioms, or invented entities are introduced beyond the palette construction already present in the literature.

axioms (1)

standard math Standard properties of 3-uniform hypergraphs and the definition of (d,μ,1)-dense sets
Invoked in the opening definitions to set up the density condition.

pith-pipeline@v0.9.0 · 5828 in / 1324 out tokens · 36144 ms · 2026-05-18T07:51:20.745985+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

palette P=(C,A) with density d(P)=|A|/|C|³ and auxiliary digraph D_P whose arcs encode (i,j)-admissible color pairs; reduction of π₁(S_k) to sup{d(P):P is S_k-bad}
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Lemma 3.2 bounding ∑(m(v)-1/2)² over high-degree vertices in T_k-free digraphs via Caro-Wei

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

[1]

Colloq., Balatonfüred, 1969), volume 4 ofColloq

W.G.BrownandF.Harary.Extremaldigraphs.InCombinatorial theory and its applications, I-III (Proc. Colloq., Balatonfüred, 1969), volume 4 ofColloq. Math. Soc. János Bolyai, pages 135–198. North-Holland, Amsterdam- London, 1970

work page 1969
[2]

Bucić, J

M. Bucić, J. W. Cooper, D. Král’, S. Mohr, and D. Munhá Correia. Uniform Turán density of cycles.Trans. Amer. Math. Soc., 376(7):4765–4809, 2023. TURÁN DENSITIES OF STARS IN UNIFORMLY DENSE HYPERGRAPHS 9

work page 2023
[3]

A. Y. Chen and B. Schülke. Beyond the broken tetrahedron. preprint arXiv:2211.12747, 2022

work page arXiv 2022
[4]

On Ramsey—Turán type theorems for hypergraphs

P. Erdős and V. T. Sós. On Ramsey-Turán type theorems for hypergraphs.Combinatorica, 2(3):289–295, 1982

work page 1982
[5]

Garbe, D

F. Garbe, D. Il’kovič, D. Král’, F. Kučerák, and A. Lamaison. Hypergraphs with uniform Turán density equal to8/27. preprint arXiv:2407.05829, 2024

work page arXiv 2024
[6]

Garbe, D

F. Garbe, D. Král’, and A. Lamaison. Hypergraphs with minimum positive uniform Turán density.Israel J. Math., 259(2):701–726, 2024

work page 2024
[7]

A problem of Erdős and Sós on 3-graphs

R. Glebov, D. Král’, and J. Volec. A problem of Erdős and Sós on 3-graphs.Israel J. Math., 211(1):349–366, 2016

work page 2016
[8]

Lamaison

A. Lamaison. Palettes determine uniform turán density. Preprint arXiv:2408.09643, 2024

work page arXiv 2024
[9]

Lamaison and Z

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

work page arXiv 2024
[10]

H. Li, H. Lin, G. Wang, and W. Zhou. Hypergraphs with a quarter uniform turán density.J. Oper. Res. Soc. China, 2025

work page 2025
[11]

A. A. Razborov. Flag algebras.Journal of Symbolic Logic, 72(4):1239–1282, 2007

work page 2007
[12]

C. Reiher. Extremal problems in uniformly dense hypergraphs.European J. Combin., 88:103117, 22, 2020

work page 2020
[13]

Reiher, V

C. Reiher, V. Rödl, and M. Schacht. Embedding tetrahedra into quasirandom hypergraphs.J. Combin. Theory Ser. B, 121:229–247, 2016

work page 2016
[14]

Hypergraphs with vanishing Turán density in uniformly dense hypergraphs

C. Reiher, V. Rödl, and M. Schacht. Hypergraphs with vanishing Turán density in uniformly dense hypergraphs. J. Lond. Math. Soc. (2), 97(1):77–97, 2018

work page 2018
[15]

Reiher, V

C. Reiher, V. Rödl, and M. Schacht. On a Turán problem in weakly quasirandom 3-uniform hypergraphs.J. Eur. Math. Soc. (JEMS), 20(5):1139–1159, 2018

work page 2018
[16]

V. Rödl. On universality of graphs with uniformly distributed edges.Discrete Math., 59(1-2):125–134, 1986

work page 1986
[17]

M. Schacht. Restricted problems in extremal combinatorics. InICM—International Congress of Mathematicians. Vol. 6. Sections 12–14, pages 4646–4658. EMS Press, Berlin, 2023. Department of Information Security, Na v al University of Engineering, Wuhan, China. Email address:haolinz6@qq.com School of Mathematics, Shandong University, Jinan, China. Email addre...

work page 2023

[1] [1]

Colloq., Balatonfüred, 1969), volume 4 ofColloq

W.G.BrownandF.Harary.Extremaldigraphs.InCombinatorial theory and its applications, I-III (Proc. Colloq., Balatonfüred, 1969), volume 4 ofColloq. Math. Soc. János Bolyai, pages 135–198. North-Holland, Amsterdam- London, 1970

work page 1969

[2] [2]

Bucić, J

M. Bucić, J. W. Cooper, D. Král’, S. Mohr, and D. Munhá Correia. Uniform Turán density of cycles.Trans. Amer. Math. Soc., 376(7):4765–4809, 2023. TURÁN DENSITIES OF STARS IN UNIFORMLY DENSE HYPERGRAPHS 9

work page 2023

[3] [3]

A. Y. Chen and B. Schülke. Beyond the broken tetrahedron. preprint arXiv:2211.12747, 2022

work page arXiv 2022

[4] [4]

On Ramsey—Turán type theorems for hypergraphs

P. Erdős and V. T. Sós. On Ramsey-Turán type theorems for hypergraphs.Combinatorica, 2(3):289–295, 1982

work page 1982

[5] [5]

Garbe, D

F. Garbe, D. Il’kovič, D. Král’, F. Kučerák, and A. Lamaison. Hypergraphs with uniform Turán density equal to8/27. preprint arXiv:2407.05829, 2024

work page arXiv 2024

[6] [6]

Garbe, D

F. Garbe, D. Král’, and A. Lamaison. Hypergraphs with minimum positive uniform Turán density.Israel J. Math., 259(2):701–726, 2024

work page 2024

[7] [7]

A problem of Erdős and Sós on 3-graphs

R. Glebov, D. Král’, and J. Volec. A problem of Erdős and Sós on 3-graphs.Israel J. Math., 211(1):349–366, 2016

work page 2016

[8] [8]

Lamaison

A. Lamaison. Palettes determine uniform turán density. Preprint arXiv:2408.09643, 2024

work page arXiv 2024

[9] [9]

Lamaison and Z

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

work page arXiv 2024

[10] [10]

H. Li, H. Lin, G. Wang, and W. Zhou. Hypergraphs with a quarter uniform turán density.J. Oper. Res. Soc. China, 2025

work page 2025

[11] [11]

A. A. Razborov. Flag algebras.Journal of Symbolic Logic, 72(4):1239–1282, 2007

work page 2007

[12] [12]

C. Reiher. Extremal problems in uniformly dense hypergraphs.European J. Combin., 88:103117, 22, 2020

work page 2020

[13] [13]

Reiher, V

C. Reiher, V. Rödl, and M. Schacht. Embedding tetrahedra into quasirandom hypergraphs.J. Combin. Theory Ser. B, 121:229–247, 2016

work page 2016

[14] [14]

Hypergraphs with vanishing Turán density in uniformly dense hypergraphs

C. Reiher, V. Rödl, and M. Schacht. Hypergraphs with vanishing Turán density in uniformly dense hypergraphs. J. Lond. Math. Soc. (2), 97(1):77–97, 2018

work page 2018

[15] [15]

Reiher, V

C. Reiher, V. Rödl, and M. Schacht. On a Turán problem in weakly quasirandom 3-uniform hypergraphs.J. Eur. Math. Soc. (JEMS), 20(5):1139–1159, 2018

work page 2018

[16] [16]

V. Rödl. On universality of graphs with uniformly distributed edges.Discrete Math., 59(1-2):125–134, 1986

work page 1986

[17] [17]

M. Schacht. Restricted problems in extremal combinatorics. InICM—International Congress of Mathematicians. Vol. 6. Sections 12–14, pages 4646–4658. EMS Press, Berlin, 2023. Department of Information Security, Na v al University of Engineering, Wuhan, China. Email address:haolinz6@qq.com School of Mathematics, Shandong University, Jinan, China. Email addre...

work page 2023