Turán densities of stars in uniformly dense hypergraphs

Basic Information

• Paper ID: 2510.12576
• Title: Turán densities of stars in uniformly dense hypergraphs
• Authors: Hao Lin, Wenling Zhou
• Classification: math.CO (Combinatorics)
• Publication Date: October 14, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.12576

Abstract

This paper investigates the Turán density problem for star structures in uniformly dense hypergraphs. For 3-uniform hypergraphs, the authors define two density concepts: $(d,\mu,\cdot)$-dense and $(d,\mu,\star)$-dense. Under these constraints, determining the $\cdot$-uniform Turán density $\pi_{\cdot}(S_k)$ and $\star$-uniform Turán density $\pi_{\star}(S_k)$ of $k$-stars $S_k$ is an important problem posed by Schacht at the 2022 ICM. The main contributions of this paper are: proving that $\pi_{\cdot}(S_k) = \frac{k^2-5k+7}{(k-1)^2}$ holds for all $k \geq 11$, and determining the $\star$-uniform Turán density for all $S_k$ except $k=4$.

Research Background and Motivation

Problem Background

The Turán problem is one of the most fundamental problems in extremal combinatorics, asking for the minimum density threshold that guarantees the existence of a certain substructure. The Turán problem for hypergraphs is particularly challenging because most known and conjectured extremal constructions contain large independent sets.

Historical Development

1. Classical Turán Problem: Due to the difficulty of the hypergraph Turán problem, Erdős and Sós proposed a variant in the 1980s, restricting attention to $F$-free 3-graphs that are uniformly dense on large vertex subsets.
2. Specific Progress:
   • Rödl (1986) conjectured $\pi_{\cdot}(K_4^{(3)}) = 1/2$, which remains unsolved
   • Glebov, Král', and Volec (2016) and Reiher, Rödl, and Schacht (2015) independently proved $\pi_{\cdot}(K_4^{(3)-}) = 1/4$
   • The latter also established bounds for general $k$-stars: $\frac{k^2-5k+7}{(k-1)^2} \leq \pi_{\cdot}(S_k) \leq \left(\frac{k-2}{k-1}\right)^2$

Research Motivation

Schacht formally posed the problem of determining $\pi_{\cdot}(S_k)$ and $\pi_{\star}(S_k)$ at the 2022 ICM. Lamaison and Wu (2024) proved that the lower bound is tight for $k \geq 48$. This paper aims to extend this result to smaller values of $k$.

Core Contributions

1. Main Theoretical Result: Proved that $\pi_{\cdot}(S_k) = \frac{k^2-5k+7}{(k-1)^2}$ holds for all $k \geq 11$
2. Extended Result: Determined $\pi_{\star}(S_k) = \frac{k^2-5k+7}{(k-1)^2}$ for all $k \geq 5$
3. Methodological Innovation: Adopted Lamaison's palette construction framework, avoiding traditional hypergraph regularity lemmas
4. Technical Breakthrough: Established critical upper bound estimates through structural analysis of auxiliary directed graphs

Methodology Details

Core Definitions

$k$-star Definition: A $k$-star $S_k$ is a 3-uniform hypergraph on $(k+1)$ vertices containing vertices $u, v_1, \ldots, v_k$ such that $uv_iv_j \in E(S_k)$ for all $1 \leq i < j \leq k$.

Density Concepts:

• $\cdot$-dense: A 3-uniform hypergraph $H=(V,E)$ is $(d,\mu,\cdot)$-dense if for any subsets $X,Y,Z \subseteq V$, the number of triples $(x,y,z) \in X \times Y \times Z$ with $\{x,y,z\} \in E$ is at least $d|X||Y||Z| - \mu|V|^3$
• $\star$-dense: For any subset $X \subseteq V$ and pair set $P \subseteq V \times V$, satisfying corresponding conditions

Palette Method

Palette Definition: A palette $P = (C,A)$ consists of a finite color set $C$ and a set of ordered triples $A \subseteq C \times C \times C$.

Key Properties:

• Density: $d(P) := |A|/|C|^3$
• Minimum degree: $\delta(P) := \min_{i \in [3], a \in C} |A_a^i|/|C|^2$

Core Theorems:

• $\pi_{\cdot}(F) = \pi_{pal}^{\cdot}(F)$ (Theorem 2.2)
• $\pi_{\star}(F) = \pi_{pal}^{\star}(F)$ (Theorem 2.3)

Auxiliary Directed Graph Construction

For a palette $P = (C,A)$, construct an auxiliary directed graph $D_P = (V,E)$:

• Vertex set: $V = C_1 \cup C_2$ (two disjoint copies of $C$)
• Edge rule: Add arcs according to the $(i,j)$-acceptability of color pairs $(a,b)$

Key Lemma: If palette $P$ is $S_k$-bad, then $D_P$ is acyclic and $T_k$-free (Lemma 2.4).

Experimental Setup

Theoretical Analysis Framework

This paper employs a purely theoretical analysis approach without experimental data. The main steps are:

1. Reduction Strategy: Reduce the main theorem to key lemmas (Lemma 2.6)
2. Structural Analysis: Analyze properties of $T_k$-free directed graphs
3. Upper Bound Estimation: Establish upper bounds through variants of the Caro-Wei theorem

Proof Techniques

• Brown-Harary Theorem: Determines the maximum number of arcs in $T_k$-free directed graphs
• Inequality Techniques: Use basic inequalities such as $xy \leq \left(\frac{x+y}{2}\right)^2$
• Case Analysis: Discuss cases based on the magnitude of $\min\{e_{2,1}(a), e_{2,3}(a)\}$

Experimental Results

Main Theorems

Theorem 1.2: $\pi_{\cdot}(S_k) = \frac{k^2-5k+7}{(k-1)^2}$ for all $k \geq 11$.

Theorem 1.4: $\pi_{\star}(S_k) = \frac{k^2-5k+7}{(k-1)^2}$ for all $k \geq 5$.

Key Lemmas

Lemma 2.6: Let $k \geq 5$. For any $S_k$-bad palette $P$ satisfying $\delta(P) \geq \frac{1}{4}$, we have $d(P) \leq \frac{k^2-5k+7}{(k-1)^2}$.

Technical Results

Lemma 3.2: Given $k \geq 4$, let $D$ be a $T_k$-free directed graph on $n$ vertices. For each vertex $v$, let $m(v) = \max\{d_D^+(v)/n, d_D^-(v)/n\}$, and set $V' = \{v \in V(D) : m(v) \geq \frac{2}{k-1}\}$. Then $\sum_{v \in V'} \left(m(v) - \frac{1}{2}\right)^2 \leq \frac{(k-3)^2}{4(k-1)^2}n$

Related Work

Historical Development

1. Erdős-Sós Problem: Proposed in 1982, restricting the Turán problem to uniformly dense hypergraphs
2. Rödl Construction: Introduced in 1986, conjecturing $\pi_{\cdot}(K_4^{(3)}) = 1/2$
3. Flag Algebra Method: Introduced by Razborov (2007), applied by Glebov et al. to solve the $K_4^{(3)-}$ problem
4. Hypergraph Regularity Method: Series of works by Reiher, Rödl, and Schacht

Recent Progress

• Lamaison Framework: Introduced in 2024, unifying the study of $\pi_{\cdot}$ and $\pi_{\star}$
• Lamaison-Wu Result: Proved the exact value for $k \geq 48$
• Computational Assistance: Suggested that the lower bound may already be tight for $k \geq 40$

Conclusions and Discussion

Main Conclusions

This paper significantly improves upon the results of Lamaison and Wu, extending the range for which $\pi_{\cdot}(S_k)$ is exactly determined from $k \geq 48$ to $k \geq 11$, and completely resolves the $\pi_{\star}(S_k)$ problem except for $k=4$.

Open Problems

The authors propose two conjectures:

1. Conjecture 5.1: $\pi_{\cdot}(S_k) = \frac{k^2-5k+7}{(k-1)^2}$ holds for all $4 \leq k \leq 10$
2. Conjecture 5.2: $\pi_{\star}(S_4) = \frac{1}{3}$

Technical Limitations

• For the case $k=4$, the condition $m(v) \geq 2/3$ is required, which is difficult to guarantee within the current framework
• The threshold $m(v) \geq 2/(k-1)$ in Lemma 3.2 is optimal for $k=4$, requiring new technical breakthroughs

In-Depth Evaluation

Strengths

1. Technical Innovation: Successfully applied the palette method, avoiding complex hypergraph regularity lemmas
2. Significant Results: Substantially extended the applicable range of known results
3. Unified Approach: Simultaneously addressed both the $\pi_{\cdot}$ and $\pi_{\star}$ problems
4. Clear Proof Structure: The structured reduction strategy makes the proof logic transparent

Weaknesses

1. Incomplete Coverage: Cases with $4 \leq k \leq 10$ remain unresolved
2. Method Limitations: The special case $k=4$ requires new techniques
3. Computational Complexity: The proof involves complex inequality estimates and case analyses

Impact

1. Theoretical Contribution: Advances fundamental problems in extremal combinatorics
2. Methodological Value: The successful application of palette techniques provides new insights for related problems
3. Future Research: Lays the foundation for completely resolving Schacht's problem

Applicable Scenarios

This method is applicable to:

1. Turán problems for forbidden substructures in hypergraphs
2. Extremal problems under uniform density conditions
3. Density estimation problems in combinatorial optimization

References

The paper cites key literature in the field, including:

• Erdős-Sós (1982): Original problem formulation
• Razborov (2007): Flag algebra method
• Series of works by Reiher, Rödl, Schacht: Establishing fundamental bounds
• Lamaison (2024): Palette framework
• Brown-Harary (1970): Turán numbers for directed graphs