2025-11-14T23:55:11.549557

Turán densities of stars in uniformly dense hypergraphs

Lin, Zhou
A $3$-uniform hypergraph (or $3$-graph) $H=(V,E)$ is $(d,μ, \text{dot})$-dense if for any subsets $X, Y, Z\subseteq V$, the number of triples $(x,y,z)\in X\times Y\times Y$ with $\{x,y,z\}$ being an edge of $H$ is at least $d|X||Y||Z|-μ|V|^3$. Similarly, we say that $H$ is $(d,μ, \text{dot-edge})$-dense if for any subset $X\subseteq V$ and every pair set $P\subseteq V\times V$, the number of pairs $(x,(y,z))\in X\times P$ with $\{x,y,z\}$ being an edge of $H$ is at least $d|X||P|-μ|V|^3$. Restricting to $\text{dot}$-dense $3$-graphs and $\text{dot-edge}$-dense $3$-graphs, determining the $\text{dot}$-uniform Turán density $π_{\text{dot}}(S_k)$ and the $\text{dot-edge}$-uniform Turán density $π_{\text{dot-edge}}(S_k)$ of the $k$-star $S_k$ for $k\ge 4$ was proposed by Schacht in ICM 2022. In particular, Reiher, Rödl and Schacht presented that $π_{\text{dot}}(S_k)\ge π_{\text{dot-edge}}(S_k)\ge \frac{k^2-5k+7}{(k-1)^2}$ for $k\ge 3$ and $π_{\text{dot}}(S_3)= π_{\text{dot-edge}}(S_3)=1/4$. Last year, Lamaison and Wu shown that $π_{\text{dot}}(S_k)=\frac{k^2-5k+7}{(k-1)^2}$ for $k\ge 48$. In this paper, we show that $π_{\text{dot}}(S_k)=\frac{k^2-5k+7}{(k-1)^2}$ for $k\ge 11$. Moreover, we determine the $\text{dot-edge}$-uniform Turán density for all $S_k$ except for $k=4$.
academic

Turán densities of stars in uniformly dense hypergraphs

基本信息

  • 论文ID: 2510.12576
  • 标题: Turán densities of stars in uniformly dense hypergraphs
  • 作者: Hao Lin, Wenling Zhou
  • 分类: math.CO (组合数学)
  • 发表时间: 2025年10月14日 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2510.12576

摘要

本文研究均匀稠密超图中星形结构的Turán密度问题。对于3-一致超图，作者定义了两种密度概念：(d,μ,⋅)(d,\mu,\cdot)-稠密和(d,μ,⋆)(d,\mu,\star)-稠密。在这些约束下，确定kk-星SkS_k的⋅\cdot-一致Turán密度π⋅(Sk)\pi_{\cdot}(S_k)和⋆\star-一致Turán密度π⋆(Sk)\pi_{\star}(S_k)是Schacht在2022年ICM上提出的重要问题。本文的主要贡献是：证明了π⋅(Sk)=k2−5k+7(k−1)2\pi_{\cdot}(S_k) = \frac{k^2-5k+7}{(k-1)^2}对所有k≥11k \geq 11成立，并确定了除k=4k=4外所有SkS_k的⋆\star-一致Turán密度。

研究背景与动机

问题背景

Turán问题是极值组合学中最基本的问题之一，询问保证某个子结构存在的最小密度阈值。对于超图的Turán问题尤其困难，因为大多数已知和猜想的极值构造都包含大的独立集。

历史发展

  1. 经典Turán问题：由于超图Turán问题的困难性，Erdős和Sós在1980年代提出了一个变种，将注意力限制在顶点大子集上均匀稠密的FF-free 3-图上。
  2. 具体进展：
    • Rödl (1986)提出π⋅(K4(3))=1/2\pi_{\cdot}(K_4^{(3)}) = 1/2的猜想，至今未解决
    • Glebov, Král'和Volec (2016)以及Reiher, Rödl和Schacht (2015)独立证明了π⋅(K4(3)−)=1/4\pi_{\cdot}(K_4^{(3)-}) = 1/4
    • 后者还建立了一般kk-星的界：k2−5k+7(k−1)2≤π⋅(Sk)≤(k−2k−1)2\frac{k^2-5k+7}{(k-1)^2} \leq \pi_{\cdot}(S_k) \leq \left(\frac{k-2}{k-1}\right)^2

研究动机

Schacht在2022年ICM上正式提出确定π⋅(Sk)\pi_{\cdot}(S_k)和π⋆(Sk)\pi_{\star}(S_k)的问题。Lamaison和Wu (2024)证明了下界对k≥48k \geq 48是紧的，本文旨在将这一结果推广到更小的kk值。

核心贡献

  1. 主要理论结果：证明了π⋅(Sk)=k2−5k+7(k−1)2\pi_{\cdot}(S_k) = \frac{k^2-5k+7}{(k-1)^2}对所有k≥11k \geq 11成立
  2. 扩展结果：确定了π⋆(Sk)=k2−5k+7(k−1)2\pi_{\star}(S_k) = \frac{k^2-5k+7}{(k-1)^2}对所有k≥5k \geq 5成立
  3. 方法创新：采用Lamaison的调色板构造框架，避免了传统的超图正则性引理
  4. 技术突破：通过辅助有向图的结构分析，建立了关键的上界估计

方法详解

核心定义

kk-星定义：kk-星SkS_k是一个(k+1)(k+1)个顶点的3-图，包含顶点u,v1,…,vku, v_1, \ldots, v_k，使得uvivj∈E(Sk)uv_iv_j \in E(S_k)对所有1≤i<j≤k1 \leq i < j \leq k成立。

密度概念：

  • ⋅\cdot-稠密：3-图H=(V,E)H=(V,E)是(d,μ,⋅)(d,\mu,\cdot)-稠密的，如果对任意子集X,Y,Z⊆VX,Y,Z \subseteq V，三元组(x,y,z)∈X×Y×Z(x,y,z) \in X \times Y \times Z且{x,y,z}∈E\{x,y,z\} \in E的数量至少为d∣X∣∣Y∣∣Z∣−μ∣V∣3d|X||Y||Z| - \mu|V|^3
  • ⋆\star-稠密：对任意子集X⊆VX \subseteq V和对集合P⊆V×VP \subseteq V \times V，满足相应条件

调色板方法

调色板定义：调色板P=(C,A)P = (C,A)包含有限颜色集CC和有序三元组集合A⊆C×C×CA \subseteq C \times C \times C。

关键性质：

  • 密度：d(P):=∣A∣/∣C∣3d(P) := |A|/|C|^3
  • 最小度：δ(P):=min⁡i∈[3],a∈C∣Aai∣/∣C∣2\delta(P) := \min_{i \in [3], a \in C} |A_a^i|/|C|^2

核心定理：

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

辅助有向图构造

对于调色板P=(C,A)P = (C,A)，构造辅助有向图DP=(V,E)D_P = (V,E)：

  • 顶点集：V=C1∪C2V = C_1 \cup C_2（CC的两个不相交副本）
  • 边规则：根据颜色对(a,b)(a,b)的(i,j)(i,j)-可接受性添加弧

关键引理：如果调色板PP是SkS_k-坏的，则DPD_P无环且TkT_k-free（Lemma 2.4）。

实验设置

理论分析框架

本文采用纯理论分析方法，不涉及实验数据。主要通过以下步骤：

  1. 归约策略：将主定理归约到关键引理（Lemma 2.6）
  2. 结构分析：分析TkT_k-free有向图的性质
  3. 上界估计：通过Caro-Wei定理的变种建立上界

证明技术

  • Brown-Harary定理：确定TkT_k-free有向图的最大弧数
  • 不等式技巧：使用xy≤(x+y2)2xy \leq \left(\frac{x+y}{2}\right)^2等基本不等式
  • 案例分析：根据最小值min⁡{e2,1(a),e2,3(a)}\min\{e_{2,1}(a), e_{2,3}(a)\}的大小分情况讨论

实验结果

主要定理

定理1.2：π⋅(Sk)=k2−5k+7(k−1)2\pi_{\cdot}(S_k) = \frac{k^2-5k+7}{(k-1)^2}对所有k≥11k \geq 11成立。

定理1.4：π⋆(Sk)=k2−5k+7(k−1)2\pi_{\star}(S_k) = \frac{k^2-5k+7}{(k-1)^2}对所有k≥5k \geq 5成立。

关键引理

引理2.6：设k≥5k \geq 5，对于任意满足δ(P)≥14\delta(P) \geq \frac{1}{4}的SkS_k-坏调色板PP，有d(P)≤k2−5k+7(k−1)2d(P) \leq \frac{k^2-5k+7}{(k-1)^2}。

技术结果

引理3.2：给定k≥4k \geq 4，设DD是nn个顶点的TkT_k-free有向图，对每个顶点vv，令m(v)=max⁡{dD+(v)/n,dD−(v)/n}m(v) = \max\{d_D^+(v)/n, d_D^-(v)/n\}，设V′={v∈V(D):m(v)≥2k−1}V' = \{v \in V(D) : m(v) \geq \frac{2}{k-1}\}，则 ∑v∈V′(m(v)−12)2≤(k−3)24(k−1)2n\sum_{v \in V'} \left(m(v) - \frac{1}{2}\right)^2 \leq \frac{(k-3)^2}{4(k-1)^2}n

相关工作

历史发展

  1. Erdős-Sós问题：1982年提出限制在均匀稠密超图上的Turán问题
  2. Rödl构造：1986年提出准随机构造，猜想π⋅(K4(3))=1/2\pi_{\cdot}(K_4^{(3)}) = 1/2
  3. 旗代数方法：Razborov (2007)引入，Glebov等人用于解决K4(3)−K_4^{(3)-}问题
  4. 超图正则性方法：Reiher, Rödl, Schacht的系列工作

近期进展

  • Lamaison框架：2024年引入调色板方法，统一了π⋅\pi_{\cdot}和π⋆\pi_{\star}的研究
  • Lamaison-Wu结果：证明了k≥48k \geq 48情况下的精确值
  • 计算辅助：表明下界对k≥40k \geq 40可能已经紧致

结论与讨论

主要结论

本文显著改进了Lamaison和Wu的结果，将精确确定π⋅(Sk)\pi_{\cdot}(S_k)的范围从k≥48k \geq 48扩展到k≥11k \geq 11，并完全解决了π⋆(Sk)\pi_{\star}(S_k)问题（除k=4k=4外）。

开放问题

作者提出两个猜想：

  1. 猜想5.1：π⋅(Sk)=k2−5k+7(k−1)2\pi_{\cdot}(S_k) = \frac{k^2-5k+7}{(k-1)^2}对所有4≤k≤104 \leq k \leq 10成立
  2. 猜想5.2：π⋆(S4)=13\pi_{\star}(S_4) = \frac{1}{3}

技术局限

  • 对于k=4k=4的情况，需要m(v)≥2/3m(v) \geq 2/3的条件，但这在当前框架下难以保证
  • 引理3.2中的阈值m(v)≥2/(k−1)m(v) \geq 2/(k-1)对k=4k=4是最优的，需要新的技术突破

深度评价

优点

  1. 技术创新：成功应用调色板方法，避免了复杂的超图正则性引理
  2. 结果显著：将已知结果的适用范围大幅扩展
  3. 方法统一：同时处理了π⋅\pi_{\cdot}和π⋆\pi_{\star}两个问题
  4. 证明清晰：结构化的归约策略使证明思路清晰

不足

  1. 覆盖不完全：仍有4≤k≤104 \leq k \leq 10的情况未解决
  2. 方法局限：对k=4k=4的特殊情况需要新的技术
  3. 计算复杂：证明涉及复杂的不等式估计和案例分析

影响力

  1. 理论贡献：推进了极值组合学中的基本问题
  2. 方法价值：调色板技术的成功应用为相关问题提供了新思路
  3. 后续研究：为完全解决Schacht问题奠定了基础

适用场景

该方法适用于：

  1. 超图中禁用子结构的Turán问题
  2. 均匀稠密条件下的极值问题
  3. 组合优化中的密度估计问题

参考文献

论文引用了该领域的关键文献，包括：

  • Erdős-Sós (1982)：提出原始问题
  • Razborov (2007)：旗代数方法
  • Reiher, Rödl, Schacht系列工作：建立基本界
  • Lamaison (2024)：调色板框架
  • Brown-Harary (1970)：有向图Turán数