均匀无并超图的紧渐近界

《European Journal of Combinatorics》：Sharp asymptotic bounds for uniform union-free hypergraphs

　　

摘要：如果一个 $r$-均齐超图满足任意两个至多包含 $t$ 条边的不同子集的并集互不相同，则称该超图为 $t$-并自由超图。$t$-并自由超图的研究有着多重来源和悠久历史，可追溯到 Kautz 和 Singleton（1964）在编码理论、Bollobás 和 Erd?s（1976）在组合学以及 Hwang 和 Sós（1987）在群检测中的工作。设 $U_t(n, r)$ 表示 $n$ 个顶点的 $t$-并自由 $r$-均齐超图中最多包含的边数。在本文中，我们确定了几乎所有 $t \geq 3$ 和 $r \geq 3$ 时 $U_t(n, r)$ 的渐近行为（精确到次低阶项）。这一结果大大推进了对该极值函数的理解，因为此前只知道 $U_2(n, 3)$ 和 $U_2(n, 4)$ 的渐近表达式。作为我们证明的关键组成部分，我们建立了近似最优的局部稀疏导出超图装箱的存在性，这一结果本身也具有独立的研究价值。

**1. 引言**

给定一个 $r$-均齐超图（简称 $r$-图）族 $\mathcal{L}$，若一个 $r$-图不包含 $\mathcal{L}$ 中任何成员的副本，则称该 $r$-图为 $\mathcal{L}$-自由的。$n$ 个顶点的 $\mathcal{L}$-自由 $r$-图的最大边数称为极值数 $\mathrm{ex}_r(n, \mathcal{L})$。Katona, Nemetz 和 Simonovits [31] 证明了对于任何 $\mathcal{L}$，Turán 密度 $\pi_r(\mathcal{L}) \coloneqq \lim_{n \to \infty} \frac{\mathrm{ex}_r(n, \mathcal{L})}{\binom{n}{r}}$ 总存在。若 $\pi_r(\mathcal{L}) > 0$，则称 $\mathcal{L}$ 为非退化的；否则称其为退化的。对于退化的 $\mathcal{L}$，若存在实数 $\alpha \in (0, r)$ 和正常数 $c_1, c_2$ 使得对所有足够大的 $n$ 有 $c_1 n^{\alpha} \leq \mathrm{ex}_r(n, \mathcal{L}) \leq c_2 n^{\alpha}$，则称 $\alpha$ 为 $\mathcal{L}$ 的 Turán 指数。此外，若极限 $\pi_r^d(\mathcal{L}) \coloneqq \lim_{n \to \infty} \frac{\mathrm{ex}_r(n, \mathcal{L})}{n^{\alpha}}$ 存在且位于 $(0, \infty)$ 中，则称 $\pi_r^d(\mathcal{L})$ 为 $\mathcal{L}$-自由 $r$-图的退化 Turán 密度。

一般而言，即使我们已知退化 $\mathcal{L}$ 的 Turán 指数，确定相应的退化密度是否存在仍是一个困难的任务，更不用说其精确值了。例如，设 $C_i$ 表示长度为 $i$ 的圈。极值图论的经典结果表明 $\mathrm{ex}_2(n, C_3) = \lfloor n^2/4 \rfloor$ [38] 和 $\mathrm{ex}_2(n, C_4) = \frac{1}{2}n^{3/2} + O(n)$ [2], [13], [35], [42]。然而，与之密切相关的 $\mathrm{ex}_2(n, \{C_3, C_4\})$ 的渐近行为至今未知。Erd?s 在 1975 年提出的一个著名猜想 [7] 断言：

$$\lim_{n \to \infty} \frac{\mathrm{ex}_2(n, \{C_3, C_4\})}{n^{3/2}} = \frac{1}{2\sqrt{2}}.$$

尽管在过去 50 年中付出了巨大努力，但进展甚微。上述极限是否存在目前尚不清楚。当前的记录为

$$\frac{1}{2\sqrt{2}}n^{3/2} + \Omega(n^{1.25}) \leq \mathrm{ex}_2(n, \{C_3, C_4\}) \leq \mathrm{ex}_2(n, C_4) = \frac{1}{2}n^{3/2} + O(n),$$

其中下界来自 Ma 和 Yang [37] 的最新工作。

本文研究的并自由超图是 $\{C_3, C_4\}$-自由图在超图上的推广。对于固定的正整数 $r$ 和 $t$，若一个 $r$-图 $H$ 满足对任意两个不同的子集 $A, B \subseteq H$（每个子集包含至多 $t$ 条边），都有 $\bigcup_{A \in \mathcal{A}} A \neq \bigcup_{B \in \mathcal{B}} B$，则称 $H$ 为 $t$-并自由的。设 $U_t(n, r)$ 表示 $n$ 个顶点的 $t$-并自由 $r$-图的最大边数。显然，一个图是 $\{C_3, C_4\}$-自由的当且仅当它是 2-并自由的，因此 $U_2(n, 2) = \mathrm{ex}_2(n, \{C_3, C_4\})$。我们的主要研究内容是探讨 $t \geq 3$ 和 $r \geq 3$ 时一般 $t$-并自由 $r$-图的退化 Turán 密度。

并自由超图的研究有着多重来源，受到编码理论 [32]、组合学 [8] 和群检测 [29] 中问题与应用的推动。从历史上看，1964 年，Kautz 和 Singleton [32] 首先提出了 $t$-并自由超图的概念，1 其动机来自信息检索和数据通信中的应用。相关领域的研究在编码理论中仍然十分活跃，参见 [5], [27], [46]。1977 年，Bollobás 和 Erd?s（见 [8] 第 11 页）在不知情的情况下提出了一个组合学问题，即确定 $n$ 个顶点的 2-并自由 $r$-图的最大边数，并证明了 $U_2(n, 3) = \Theta(n^2)$。1987 年，Hwang 和 Sós [29] 引入了与之密切相关的 $t$-Sidon 族的概念。一个超图具有该性质是指任意两个恰好包含 $t$ 条边的不同子集具有不同的并集。

对于 2-并自由超图，Frankl 和 Füredi 确定了极限 $\lim_{n \to \infty} \frac{U_2(n, 3)}{n^2} = \frac{1}{6}$ [17] 和 $\lim_{n \to \infty} \frac{U_2(n, 4)}{n^3} = \frac{1}{24}$ [18]。据我们所知，这些是已知 $U_t(n, r)$ 的精确渐近界的唯二情形。在 [18] 中，Frankl 和 Füredi 还证明了

$$U_2(n, r) = \Theta\left(n^{\lceil 4r/3 \rceil / 2}\right).$$

对于 $t \geq 3$，$t$-并自由超图与一种被广泛研究的组合对象——覆盖自由超图密切相关，该概念由 Kautz 和 Singleton [32] 以及 Erd?s, Frankl 和 Füredi [9], [10] 独立提出。若一个 $r$-图 $H$ 中没有任何一条边被另外 $t$ 条不同边的并集所包含，则称 $H$ 为 $t$-覆盖自由的。覆盖自由和并自由超图在编码理论、群检测和密码学中有各种应用。更多细节请参考综述 [30]。

以下事实连接了并自由超图和覆盖自由超图 [23]。

**引理.** 若 $H$ 是 $t$-覆盖自由的，则它是 $t$-并自由的；若 $H$ 是 $t$-并自由的，则它是 $(t-1)$-覆盖自由的。

设 $F_t(n, r)$ 表示 $n$ 个顶点的 $t$-覆盖自由 $r$-图的最大边数。由上述引理可得

$$F_t(n, r) \leq U_t(n, r) \leq F_{t-1}(n, r).$$

Frankl 和 Füredi [19] 证明了 $F_t(n, r)$ 对所有 $t \geq 2, r \geq 3$ 的精确渐近界，即

$$\lim_{n \to \infty} \frac{F_t(n, r)}{n^{\lceil rt \rceil}} = \frac{1}{\lceil rt \rceil !} \cdot \frac{1}{\binom{r}{\lceil rt \rceil} - m(r, \lceil rt \rceil, \lambda)},$$

其中 $0 \leq \lambda \leq t-1$ 是唯一满足 $r = \lceil rt \rceil(\lambda + 1) + (\lceil rt \rceil - 1)(t - \lambda - 1)$ 的整数，而对于正整数 $n, r, \lambda$，$m(n, r, \lambda)$ 是 $n$ 个顶点的 $r$-图中不包含 $\lambda + 1$ 条两两不相交边的最大边数（即匹配数至多为 $\lambda$）。

由 (3), (4) 可得

$$\Omega(n^{\lceil rt \rceil}) = F_t(n, r) \leq U_t(n, r) \leq F_{t-1}(n, r) = O(n^{\lceil r(t-1) \rceil}).$$

对于不同的参数范围，(5) 已有若干改进。2013 年，Füredi 和 Ruszinkó [23] 证明了 $t = r$ 的情形下接近二次增长，即对 $r \geq 4$ 证明了 $n^{2-o(1)} < U_r(n, r) = O(n^2)$，并证明了 $U_3(n, 3) = \Omega(n^{5/3})$。他们还猜想 $U_r(n, r) = o(n^2)$（见 [23, 猜想 1.11]）。2020 年，Shangguan 和 Tamo [44] 证明了对所有 $t \geq 3$ 和 $r \geq 3$，

$$U_t(n, r) = \Omega(n^{rt-1}).$$

将 (3), (4), (5) 和 (6) 结合起来，不难看出对 $t \geq 2, k \geq 2$ 和 $0 \leq a \leq t-1$，

$$\Omega\left(n^{\max\{\lceil tk-a \rceil, tk-a\}}\right) = U_{t+1}(n, tk-a) \leq F_t(n, tk-a) \leq \frac{1}{k!} \cdot \frac{1}{\binom{tk-a}{k} - m(tk-a, k, t-a-1)} \cdot n^k + o(n^k).$$

注意为方便记号，在 (7) 及下文我们使用 $U_{t+1}(n, \cdot)$ 代替 $U_t(n, \cdot)$。

我们的主要贡献是 $U_{t+1}(n, r)$ 的一个新的下界，表明对几乎所有 $t \geq 2, r \geq 3$，除了 $\{U_3(n, 2s-1), U_{s+1}(n, s+1), U_{s+1}(n, s+2) : s \geq 2\}$ 和 $U_4(n, 7)$ 之外，(7) 中的上界在低阶项意义下是渐近最优的。换句话说，我们确定了这些并自由超图的退化 Turán 密度。

**定理 1.1** 设 $t \geq 2, k \geq 2$ 和 $0 \leq a \leq t-1$ 为整数。则

$$\lim_{n \to \infty} \frac{U_{t+1}(n, tk-a)}{n^k} = \frac{1}{k!} \cdot \frac{1}{\binom{tk-a}{k} - m(tk-a, k, t-a-1)},$$

除了 $(t+1, tk-a) \in \{(3, 2s-1), (s+1, s+1), (s+1, s+2) : s \geq 2\} \cup \{(4, 7)\}$ 的情形。

下面简要讨论 $m(r, k, \lambda)$ 的精确值。1965 年，Erd?s [6] 提出了以下著名的猜想。

**猜想 1.2** Erd?s 匹配猜想 [6]
对所有正整数 $r, k, \lambda$ 且 $r \geq (\lambda+1)k$，有

$$m(r, k, \lambda) = \max\left(\binom{r}{k} - \binom{r-\lambda k}{k}, \binom{(\lambda+1)k-1}{k}\right).$$

该猜想已被广泛研究，目前已部分解决，参见 [1], [14], [15], [16], [20], [21], [28], [33], [34], [39] 及其中的参考文献。当 $\lambda = 0$ 时，显然有 $m(r, k, 0) = 0$。当 $\lambda = 1$ 时，著名的 Erd?s-Ko-Rado 定理 [12] 给出 $m(r, k, 1) = \binom{r-1}{k-1}$。当 $k = 2, 3$ 时，该猜想分别由 Erd?s 和 Gallai [11] 以及 Frankl [15] 解决。最近，Frankl, Lu, Ma 和 Wu [21] 以及 Hou, Hu 和 Liu [28] 在 $k = 4$ 的情形下取得了实质性进展。对于一般的 $k$，当前记录见 [14], [16], [20], [33]。

将 $m(tk-a, k, t-a-1)$ 的精确值代入定理 1.1，即可得到相应极限 $\lim_{n \to \infty} \frac{U_{t+1}(n, tk-a)}{n^k}$ 的精确值。我们列出其中的一些结果如下。

**推论 1.3** 在定理 1.1 的条件下，并排除该定理中列出的例外情形，则以下关于 $\lim_{n \to \infty} \frac{U_{t+1}(n, tk-a)}{n^k}$ 的显式值成立：

- 对于 $k = 2$，Erd?s 和 Gallai [11] 证明了 $m(2t-a, 2, t-a-1) = \max\left(\binom{2t-2a-1}{2}, \binom{2t-a}{2} - \binom{t+1}{2}\right)$。因此由定理 1.1，当 $t \leq 3a+2$ 时，

$$\lim_{n \to \infty} \frac{U_{t+1}(n, 2t-a)}{n^2} = \frac{1}{2} \cdot \frac{1}{\binom{t+1}{2}},$$

当 $t > 3a+2$ 时，

$$\lim_{n \to \infty} \frac{U_{t+1}(n, 2t-a)}{n^2} = \frac{1}{2} \cdot \frac{1}{\binom{2t-a}{2} - \binom{2t-2a-1}{2}}.$$

- 对于 $k = 3$，Frankl [15] 证明了 $m(3t-a, 3, t-a-1) = \max\left(\binom{3t-3a-1}{3}, \binom{3t-a}{3} - \binom{2t+1}{3}\right)$。因此由定理 1.1，当 $-26a^2 + 46at - 25a - 8t^2 + 19t - 6 \geq 0$ 时，

$$\lim_{n \to \infty} \frac{U_{t+1}(n, 3t-a)}{n^3} = \frac{1}{6} \cdot \frac{1}{\binom{2t+1}{3}},$$

当 $-26a^2 + 46at - 25a - 8t^2 + 19t - 6 < 0$ 时，

$$\lim_{n \to \infty} \frac{U_{t+1}(n, 3t-a)}{n^3} = \frac{1}{6} \cdot \frac{1}{\binom{3t-a}{3} - \binom{3t-3a-1}{3}}.$$

- 当 $a = 0$ 时，Kleitman [33] 证明了 $m(tk, k, t-1) = \binom{tk-1}{k}$。因此 $\lim_{n \to \infty} \frac{U_{t+1}(n, tk)}{n^k} = \frac{1}{k!} \cdot \frac{1}{\binom{tk-1}{k} - \binom{tk-1}{k-1}}$（注：原文如此，可能涉及进一步化简）。

- 当 $tk - a \geq (2(t-a-1)+1)k - (t-a-1)$，等价于 $\frac{t-1}{2} \leq a \leq t-1$ 时，Frankl [14] 证明了 $m(tk-a, k, t-a-1) = \binom{tk-a}{k} - \binom{tk-a-(t-a-1)k}{k}$。因此 $\lim_{n \to \infty} \frac{U_{t+1}(n, tk-a)}{n^k} = \frac{1}{k!} \cdot \frac{1}{\binom{t(k-1)+1}{k}}$。

**证明思路.** 定理 1.1 中下界的证明基于超图装箱方法（正式定义见第 2 节），这是一种建立概率下界的有力技术。据我们所知，该研究方向始于 Frankl 和 R?dl [22]，他们证明了对于任意固定超图 $J$，存在近最优的 $J$-装箱，推广了 R?dl 关于近似 Steiner 系存在性的工作 [43]。后来，Frankl 和 Füredi [19] 将该结果推广为近最优的导出 $J$-装箱，并利用它们建立了覆盖自由超图的精确渐近下界（见 (4)）。基于 Delcourt 和 Postle [4] 以及 Glock, Joos, Kim, Kühn 和 Lichev [24] 独立证明的一个有力结果（见引理 2.3），我们通过证明近最优的局部稀疏导出 $J$-装箱的存在性（见引理 3.1）来强化 [19]，并应用它推导出并自由超图的精确渐近下界。类似的局部稀疏装箱结果最近被多位作者用于研究 Brown-Erd?s-Sós 极值超图问题（详见 [3], [25], [26], [36], [40]）。

**文章组织.** 本文组织如下。在第 2 节中，我们给出必要的定义，并简要介绍超图装箱和匹配的历史。我们还陈述了 [4], [24] 中关于无冲突超图匹配的一个有用引理（引理 2.3）。在第 3 节中，利用引理 2.3 建立了我们的主要技术引理（引理 3.1），即局部稀疏导出超图装箱的存在性。定理 1.1 中下界的证明分为 $a = 0$ 的情形（在第 4 节证明）和 $1 \leq a \leq t-1$ 的情形，后者技术上较为简单，证明延迟至附录 A。最后，我们在第 5 节中提出了一些开放问题。

**2. 预备知识**

全文中，我们假设 $r, t, k, v, e$ 为固定正整数且 $n \to \infty$。我们用 $[n]$ 表示集合 $\{1, \ldots, n\}$。对于有限集 $V$，我们用 $\binom{V}{r}$ 表示 $V$ 的所有 $r$-元子族的集合。定义在顶点集 $V(H)$ 上的 $r$-图 $H$ 是 $V(H)$ 的不同 $r$-元子集的族，即 $H \subseteq \binom{V(H)}{r}$。

记两个有限子集 $B, C$ 的对称差为 $B \triangle C \coloneqq (B \setminus C) \cup (C \setminus B)$。

**(v,e)-自由超图.** 一个 $(v, e)$-配置是一个由 $e$ 条不同边组成的族，其并集至多包含 $v$ 个顶点。若一个 $r$-图 $H$ 不包含任何 $(v, e)$-配置，则称 $H$ 为 $(v, e)$-自由的，即对任意 $e$ 条不同的边 $A_1, \ldots, A_e \in H$，有 $|\bigcup_{i=1}^e A_i| \geq v+1$。$(v, e)$-自由超图也称为局部稀疏的。

以下引理保证了存在一个 $m$ 个顶点的、具有大量边的局部稀疏 $r$-图。大量边是为了在我们构造中获得期望的下界，而局部稀疏性则排除了可能导致并自由性失败的小配置。

**引理 2.1** 参见 [45] 中命题 6
对所有固定整数 $r > k \geq 2$ 和 $e \geq 2$，存在 $r$-图 $G \subseteq \binom{[m]}{r}$，至少有 $\frac{c}{m} \cdot \binom{m}{k+1} \cdot e-1$ 条边，且对 $2 \leq \ell \leq e$ 均为 $(\ell r - (\ell-1)k - 1, \ell)$-自由的，其中 $c = c(r, k, e)$ 是与 $m$ 无关的绝对常数。

**超图装箱和匹配.** 下面给出超图装箱和匹配的若干定义。

**定义 2.2 装箱和导出装箱**
对于固定的 $k$-图 $J$，$\binom{[n]}{k}$ 中的 $J$-装箱 $\mathcal{P}$ 是一族边不相交的 $J$ 的副本，即 $\mathcal{P} = \{(V(J_i), J_i) : i \in [|P|]\}$，其中对每个 $i$，$J_i \subseteq \binom{[n]}{k}$ 是 $J$ 的一个副本，且对不同 $i, i'$，$J_i \cap J_{i'} = \emptyset$。

若对所有不同的 $i, i'$，$|V(J_i) \cap V(J_{i'})| \leq k$，且若 $|V(J_i) \cap V(J_{i'})| = k$，则 $V(J_i) \cap V(J_{i'})$ 既不是 $J_i$ 中的边也不是 $J_{i'}$ 中的边，则进一步称 $J$-装箱 $\mathcal{P}$ 为导出的。

若 $J$ 有 $m$ 个顶点且 $e \geq 2$，则称 $\binom{[n]}{k}$ 中的 $J$-装箱 $\mathcal{P} = \{(V(J_i), J_i) : i \in [|P|]\}$ 为 $e$-局部稀疏的，若 $m$-图 $\{V(J_i) : i \in [|P|]\} \subseteq \binom{[n]}{m}$ 对每个 $2 \leq \ell \leq e$ 均为 $(\ell m - (\ell-1)k - 1, \ell)$-自由的。

由于 $J$-装箱中的 $k$-图两两边不相交，$\binom{[n]}{k}$ 中任何 $J$-装箱至多包含 $\binom{n}{k} |J|$ 个 $J$ 的副本。R?dl [43]、Frankl 和 R?dl [22] 以及 Pippenger（见 [41]）具有影响力的工作表明这个平凡上界实际上是紧的：存在包含至少 $(1-o(1)) \cdot \binom{n}{k} |J|$ 个边不相交 $J$ 副本的近最优 $J$-装箱，其中 $o(1) \to 0$ 当 $n \to \infty$。Frankl 和 Füredi [19] 强化了该结果，证明了近最优的导出 $J$-装箱的存在性。

最近，Delcourt 和 Postle [4] 以及独立地 Glock, Joos, Kim, Kühn 和 Lichev [24] 通过建立一般框架大大拓展了上述工作，证明了近最优 $J$-装箱（避免某些小配置）的存在性。我们在证明 $U_t(n, r)$ 下界时也应用了这一框架。

在陈述 [4], [24] 的结果之前，我们需要一些准备工作。对于实数 $a, b \in (0, 1)$，若 $a \in [1-b, 1+b]$，则写 $a = 1 \pm b$。对于整数 $r \geq 1$，若超图每条边的规模至多为 $r$，则称其为 $r$-有界的。对于超图 $\mathcal{C}$（不一定均齐）和整数 $\ell \geq 1$，令 $\mathcal{C}^{(\ell)}$ 表示 $\mathcal{C}$ 中由 $\ell$-元边构成的子超图，即 $V(\mathcal{C}^{(\ell)}) = V(\mathcal{C})$ 且 $\mathcal{C}^{(\ell)} = \{C \in \mathcal{C} : |C| = \ell\}$。对于子集 $X \subseteq V(\mathcal{C})$，令 $\deg_{\mathcal{C}}(X)$ 表示包含 $X$ 的 $\mathcal{C}$ 中的边数，即 $\deg_{\mathcal{C}}(X) = |\{C \in \mathcal{C} : X \subseteq C\}|$。若 $X = \{v\}$ 是单个顶点，则写 $\deg_{\mathcal{C}}(v) = \deg_{\mathcal{C}}(\{v\})$。

设 $\Delta_{\ell}(C)$ 为所有 $X \in \binom{V(C)}{\ell}$ 上 $\deg_C(X)$ 的最大值。给定超图 $H$，$H$ 中的一个匹配是 $H$ 的边集中两两不相交边的集合。设 $C$ 是定义在 $H$ 的边上的一个超图。若匹配 $M \subseteq H$ 不包含 $C$ 作为子超图，则称 $M$ 是 $C$-自由的。这样的匹配称为冲突自由超图匹配 [4], [24]。下面的引理给出了超图 $H$ 存在近似最优 $C$-自由匹配的充分条件。在我们的应用中，匹配给出所需的密铺，而禁止冲突 $C$ 编码了局部稀疏性条件。

**引理 2.3** 参见文献 [4] 中的推论 1.17 和文献 [24] 中的定理 1.3

对任意整数 $r, e \geq 2$ 以及任意实数 $\epsilon > 0$，存在整数 $D_0 \geq 0$ 和实数 $\alpha > 0$，使得对任意 $D \geq D_0$，以下结论成立。设 $H$ 为一个 $r$-受限多超图，满足 $\Delta(H) \leq D$ 且 $\Delta_2(H) \leq D^{1-\epsilon}$。设 $C$ 是一个超图，$V(C) = H$，使得每个 $C \in C$ 满足 $2 \leq |C| \leq e$，且以下条件成立：

(i) 对所有 $2 \leq \ell \leq e$，$\Delta_1(C^{(\ell)}) \leq \alpha D^{\ell-1} \log D$；

(ii) 对所有 $2 \leq \ell' < \ell \leq e$，$\Delta_{\ell'}(C^{(\ell)}) \leq D^{\ell-\ell'-\epsilon}$；

(iii) 对所有 $H_2 \in H$ 和 $v \in V(H)$，$|\{H_1 \in H : \{H_1, H_2\} \in C, v \in H_1\}| \leq D^{1-\epsilon}$；

(iv) 对所有不相交的 $H_2, H_3 \in H$，$|\{H_1 \in H : \{H_1, H_2\}, \{H_1, H_3\} \in C\}| \leq D^{1-\epsilon}$。

则存在 $H$ 的一个 $C$-自由匹配，其大小至少为 $|H| D^{(1-D^{-\alpha})}$。

**3. 局部稀疏导出超图密铺**

在本节中，我们给出定理 1.1 证明中所用的主要技术引理。该引理表明，对任意固定至多两条边的 $k$-图 $J$，存在一个近似最优的导出 $J$-密铺，该密铺避免小 $(v, e)$-配置。

**引理 3.1** 设 $m > k, e \geq 2$ 为固定整数，$J$ 为定义在 $m$ 个顶点上的一个固定 $k$-图，且 $J$ 至少包含 2 条边。则对任意 $\epsilon > 0$，存在整数 $n_0$ 使得以下结论对所有 $n \geq n_0$ 成立。存在 $([n]^k)$ 中的一个 $J$-密铺 $P = \{(V(J_i), J_i) : i \in [|P|]\}$ 满足以下条件：

(i) $P$ 是导出的；

(ii) $P$ 是 $e$-局部稀疏的；

(iii) $P$ 是近似最优的，即 $|P| \geq (1-\epsilon) \binom{n}{k} / |J|$。

引理 3.1 在添加局部稀疏性条件的基础上强化了几个经典密铺结果。具体而言，R?dl [43]、Frankl 和 R?dl [22]、以及 Pippenger [41] 的工作建立了近似最优密铺的存在性，即条件 (iii) 所要求的。Frankl 和 Füredi [19] 进一步证明这样的密铺可以选择为导出的，从而得到条件 (i) 和 (iii)。引理 3.1 增加了局部稀疏性条件 (ii)，因此包含上述结果作为特例。

下面，我们给出引理 3.1 的证明，其中应用了引理 2.3。

**3.1 引理 3.1 的证明**

在整个证明过程中，我们假设 $n$ 充分大。选取一个常数 $\gamma \in (0, \min\{\epsilon/8, 1/(2(m-k))\})$。以概率 $\gamma$ 将完全 $k$-图 $([n]^k)$ 的每条边染为红色，以概率 $1-\gamma$ 染为蓝色。所有染色相互独立。设 $H$ 为一个标记的 $|J|$-均匀多超图，其顶点为 $([n]^k)$ 中染为蓝色的边。$H$ 的边为 $J$ 的标记副本 $J'$（满足 $V(J') \subseteq [n]$），使得 $J'$ 的每条边都被染为蓝色，且 $(V(J')^k) \setminus J'$ 中的每条非边都被染为红色。此处及证明中，不同的标记副本被视为 $H$ 中不同的平行边，即使它们在 $H$ 中具有相同的顶点集。$H$ 中所有度数均按重数计算。

为建立引理 3.1(ii)，我们定义一个冲突超图 $C$，其顶点为 $H$ 的标记边。$C$ 的边（我们称为冲突）是 $H$ 中 $J$ 的标记副本的集合，其顶点集构成一个极小坏配置；即其顶点集构成一个 $(\ell m - (\ell-1)k - 1, \ell)$-配置（某个 $2 \leq \ell \leq e$），但不包含任何 $(\ell' m - (\ell'-1)k - 1, \ell')$-配置（$1 \leq \ell' < \ell$）。更精确地，

$$C := \bigcup_{\ell=2}^{e} \left\{ \{J_1, \ldots, J_\ell\} \in \binom{H}{\ell} : \left|\bigcup_{i=1}^{\ell} V(J_i)\right| \leq \ell m - (\ell-1)k - 1, \ \left|\bigcup_{i \in S} V(J_i)\right| \geq |S|m - (|S|-1)k \text{ 对所有 } \emptyset \neq S \subsetneq [\ell] \right\}. \tag{9}$$

以下命题将 $H$ 中的匹配与 $([n]^k)$ 中的 $J$-密铺联系起来。

**命题 3.2** $H$ 中的每个 $C$-自由匹配都给出 $([n]^k)$ 中的一个 $J$-密铺，满足引理 3.1(i) 和 (ii)。

**证明** 设 $M$ 为 $H$ 中的一个 $C$-自由匹配。$M$ 中的边是 $J$ 的标记副本。注意 $H$ 中的平行边不可能同时属于 $M$，因为它们在 $H$ 中具有相同的顶点集。这些副本作为 $([n]^k)$ 中的 $k$-图是两两无边交的，因为它们作为 $H$ 中的边是两两无顶点交的。因此，$M$ 中的边给出 $([n]^k)$ 中的一个 $J$-密铺。记此密铺为 $P$。

我们首先证明 $P$ 是 $e$-局部稀疏的。反设 $P$ 不是 $e$-局部稀疏的，则存在子族 $Q \subseteq P$ 满足 $2 \leq |Q| \leq e$ 且 $\left|\bigcup_{J' \in Q} V(J')\right| \leq |Q|m - (|Q|-1)k - 1$。选取满足此条件的最小子族 $Q$。则 $Q$ 的每个非空真子族 $Q' \subsetneq Q$ 满足 $\left|\bigcup_{J' \in Q'} V(J')\right| \geq |Q'|m - (|Q'|-1)k$。因此这个极小子族 $Q \subseteq P$ 是 $C$ 中属于 $M$ 的一条边，与 $M$ 是 $C$-自由的矛盾。故 $P$ 是 $e$-局部稀疏的。

最后证明 $P$ 是导出的。设 $J'$ 和 $J''$ 为 $P$ 中两个不同的 $J$ 的副本。由于 $P$ 满足引理 3.1(ii) 且 $\ell = 2$，我们有 $|V(J') \cap V(J'')| \leq k$。接下来证明若 $|V(J') \cap V(J'')| = k$，则 $V(J') \cap V(J'')$ 既不是 $J'$ 中的边也不是 $J''$ 中的边。反设 $V(J') \cap V(J'')$ 是 $J'$ 中的一条边，则按定义它在 $J'$ 中被染为蓝色。然而由于 $J'$ 和 $J''$ 是无边交的 $J$ 的副本，$V(J') \cap V(J'')$ 是 $J''$ 的一条非边，因此在 $J''$ 中必须被染为红色，矛盾。由对称性，$V(J') \cap V(J'')$ 也不是 $J''$ 中的边。因此 $P$ 是导出的。 $\square$

由命题 3.2，要证明引理 3.1，只需证明 $H$ 中存在近似最优的 $C$-自由匹配。由 $H$ 的定义，$|V(H)| = \sum_{K \in \binom{[n]}{k}} X_K$ 是 $\binom{n}{k}$ 个独立指示随机变量之和，其中 $X_K = 1$ 若 $K$ 被染为蓝色，$X_K = 0$ 若 $K$ 被染为红色。显然 $E[|V(H)|] = (1-\gamma)\binom{n}{k}$，由 Chernoff 界，以高概率我们有 $|V(H)| = (1 \pm 2\gamma)\binom{n}{k}$。

**命题 3.3** 以高概率，$H$ 中每个顶点都包含在 $(1 \pm d^{-\gamma})d$ 条边中，其中 $d = (c + o(1))n^{m-k}$，$c$ 为依赖于 $J, \gamma, m, k$ 的常数。

命题 3.3 的证明推迟至附录 B。

记 $D := (1 + d^{-\gamma})d = (c + o(1))n^{m-k}$。我们应用引理 2.3，取 $r = |J|$，$\epsilon = \gamma$。命题 3.3 给出以高概率 $\Delta(H) \leq D$。接下来估计 $\Delta_2(H)$。设 $T_1, T_2 \in V(H)$ 为不同的顶点，则 $|T_1 \cup T_2| \geq k+1$。$H$ 中包含 $T_1$ 和 $T_2$ 的边是 $J$ 的标记副本，其基础顶点集包含 $T_1 \cup T_2$。对每个固定的基础顶点集，这样的标记副本只有常多个，其中常数仅依赖于 $J$。此计数包括平行边。因此，存在常数 $C_0 = C_0(J)$ 使得

$$\deg_H(\{T_1, T_2\}) = |\{J' \in E(H) : \{T_1, T_2\} \subseteq J'\}| \leq C_0 n^{m-k-1} \leq D^{1-\gamma},$$

最后一个不等式对所有充分大的 $n$ 成立，因为 $\gamma < 1/(2(m-k))$。从而 $\Delta_2(H) \leq D^{1-\gamma}$。

最后验证 $H$ 和 $C$ 满足引理 2.3(i)-(iv)。固定一条边 $\{J_1, \ldots, J_\ell\} \in C$ 和一个集合 $S \subsetneq [\ell]$ 满足 $1 \leq |S| = \ell' < \ell$。则 $\bigcup_{i \in [\ell]\setminus S} V(J_i)$ 在 $\bigcup_{i \in S} V(J_i)$ 之外至多包含 $(\ell - \ell')(m-k) - 1$ 个顶点。事实上，

$$\left|\bigcup_{i \in [\ell]\setminus S} V(J_i) \setminus \bigcup_{j \in S} V(J_j)\right| = \left|\bigcup_{i \in [\ell]} V(J_i) \setminus \bigcup_{j \in S} V(J_j)\right| \leq (\ell m - (\ell-1)k - 1) - (\ell' m - (\ell'-1)k) = (\ell - \ell')(m-k) - 1, \tag{10}$$

其中不等式由 $C$ 的定义（参见 (9)）得出。因此存在常数 $C_1 = C_1(J, e)$ 使得对固定的 $1 \leq \ell' < \ell$ 以及 $S \subseteq V(C) = H$ 的任意大小为 $\ell'$ 的子集，有

$$\deg_C^{(\ell)}(S) = \left|\{\{J_1, \ldots, J_\ell\} \in C^{(\ell)} : S \subseteq \{J_1, \ldots, J_\ell\}\}\right| \leq C_1 n^{(\ell - \ell')(m-k) - 1}, \tag{11}$$

其中不等式由 (10) 得出。事实上，给定 $S$，集合 $(\bigcup_{J_i \in \{J_1, \ldots, J_\ell\}} V(J_i)) \setminus (\bigcup_{J_i \in S} V(J_i))$ 的选择至多有 $n^{(\ell-\ell')(m-k)-1}$ 种，且在任意固定顶点集上只有常多个标记副本。因此在 (11) 中取 $\ell' = 1$，得对充分大的 $n$，

$$\Delta_1(C^{(\ell)}) \leq C_1 n^{(\ell-1)(m-k)-1} \leq \alpha D^{\ell-1} \log D,$$

验证了引理 2.3(i)。类似地，由 $\gamma < 1/(2(m-k))$ 的选择，对所有 $2 \leq \ell' < \ell$，有

$$\Delta_{\ell'}(C^{(\ell)}) \leq C_1 n^{(\ell - \ell')(m-k) - 1} \leq D^{\ell - \ell' - \gamma},$$

验证了引理 2.3(ii)。最后，引理 2.3(iii)、(iv) 平凡成立，因为由 (10) 可得 $\Delta_1(C^{(2)}) \leq C_1 n^{m-k-1} \leq D^{1-\gamma}$。

已验证 $H$ 和 $C$ 满足引理 2.3 的所有条件，我们得出结论：对充分大的 $n$，存在 $C$-自由匹配 $M \subseteq H$ 满足 $|M| \geq |H| D^{(1-D^{-\alpha})}$。由于 $H$ 是 $|J|$-均匀的且每个顶点的度数至少为 $(1-d^{-\gamma})d$，有

$$|J| \cdot |H| = \sum_{T \in V(H)} \deg_H(T) \geq (1-d^{-\gamma})d \cdot |V(H)|.$$

因此，

$$|M| \geq \frac{1-d^{-\gamma}}{1+d^{-\gamma}} (1-D^{-\alpha}) \frac{|V(H)|}{|J|} \geq \frac{1-d^{-\gamma}}{1+d^{-\gamma}} (1-D^{-\alpha}) \frac{(1-2\gamma)\binom{n}{k}}{|J|} \geq (1-\epsilon) \frac{\binom{n}{k}}{|J|},$$

最后一个不等式对充分大的 $n$ 成立，使用了 $\gamma < \epsilon/8$ 以及 $d^{-\gamma}, D^{-\alpha} = o(1)$。 $\square$

**4. 定理 1.1 的证明（$a = 0$ 情形）**

本节证明定理 1.1 中 $U_{t+1}(n, tk)$ 的下界。设 $t \geq 2$，$k \geq 2$ 为固定整数。只需证明对任意 $\epsilon > 0$，存在整数 $n_0$ 使得对所有 $n \geq n_0$，

$$U_{t+1}(n, tk) \geq (1-\epsilon) \cdot \binom{n}{k} \binom{tk-1}{k-1}. \tag{12}$$

我们的证明基于以下构造。设 $F$ 为一个固定的 $r$-图。$F$ 的 $k$-阴影，记为 $\sigma_k(F)$，由 $V(F)$ 中所有被 $F$ 的至少一个成员包含的 $k$-子集组成；换言之，$\sigma_k(F) = \bigcup_{F \in \mathcal{F}} \binom{F}{k}$。

**构造 4.1** 设 $F$ 为一个固定的 $r$-图，$\sigma_k(F)$ 为其 $k$-阴影。设 $P = \{(V(J_i), J_i) : i \in [|P|]\}$ 为 $([n]^k)$ 中的一个 $\sigma_k(F)$-密铺，其中各 $J_i$ 是 $\sigma_k(F)$ 的两两无边交副本，顶点集为 $V(J_i)$。在每个 $J_i$ 上方放置 $F$ 的一个副本 $F_i$，使得 $\sigma_k(F_i) = J_i$ 且 $V(F_i) = V(J_i)$，令

$$H(\mathcal{F}) = \bigcup_{i=1}^{|P|} F_i. \tag{13}$$

则 $H(\mathcal{F}) \subseteq ([n]^r)$ 是由 $F$ 的无边交副本的并集构成的一个 $r$-图。

我们的策略是证明如果 $F$ 和 $P$ 具有某些良好性质，则上述 $r$-图（例如 $r = tk$）$H(\mathcal{F})$ 满足以下两个性质：

(i) $H(\mathcal{F})$ 是 $(t+1)$-联集自由的；

(ii) 边数 $|H(\mathcal{F})| = |P| \cdot |F|$ 达到下界 (12) 的要求。

主要困难在于为 $F$ 和 $P$ 建立正确的性质。

$F$ 的性质由以下引理刻画。

**引理 4.2** 给定整数 $t \geq 2$, $k \geq 2$ 和实数 $\epsilon \in (0, 1)$，存在整数 $m_0$ 使得对任意 $m \geq m_0$，存在非空的 $tk$-图 $F \subseteq ([m]^{tk})$ 满足以下性质：

(i) $F$ 是 $(t+1)$-联集自由的；

(ii) $F$ 对任意 $2 \leq \ell \leq 2t+2$ 是 $(\ell \cdot tk - (\ell-1)k - 1, \ell)$-自由的；

(iii) $|F| / |\sigma_k(F)| \geq (1 - \epsilon/2) \cdot \binom{tk-1}{k-1}$。

现在简要说明引理 4.2 背后的直觉。$H(\mathcal{F})$ 中违反 $(t+1)$-联集自由性的配置可能由来自 $F$ 的单个副本或不同副本的边组成。性质 (i) 排除了第一种情况，而性质 (ii) 连同 $P$ 的局部稀疏性排除了第二种情况。性质 (iii) 控制了 $H(\mathcal{F})$ 中的边数。将其与近似最优的 $\sigma_k(F)$-密铺 $P$（满足 $|P| \geq (1-\epsilon/2) \cdot \binom{n}{k} / |\sigma_k(F)|$）结合，得到

$$|H(\mathcal{F})| = |P| \cdot |F| \geq (1-\epsilon/2) \cdot \frac{\binom{n}{k} \cdot |F|}{|\sigma_k(F)|} \geq (1-\epsilon) \cdot \binom{n}{k} \binom{tk-1}{k-1}, \tag{14}$$

因此条件 (iii) 连同 $P$ 的近似最优性给出 $|H(\mathcal{F})|$ 所需下界。

剩下的是验证上述 $F$ 和 $P$ 的性质确实蕴含 $H(\mathcal{F})$ 是 $(t+1)$-联集自由的。这由以下引理完成。

**引理 4.3** 设 $F \subseteq ([m]^{tk})$ 为满足引理 4.2(i)、(ii) 的 $tk$-图，$P = \{(V(J_i), J_i) : i \in [|P|]\}$ 为导出的、$(2t+2)$-局部稀疏的 $\sigma_k(F)$-密铺。则构造 4.1 中定义的 $tk$-图 $H(\mathcal{F})$ 是 $(t+1)$-联集自由的。

**定理 1.1 的证明（$a = 0$ 情形）**

给定整数 $t \geq 2$, $k \geq 2$ 和实数 $\epsilon \in (0, 1)$，选取 $m$ 充分大，令 $F \subseteq ([m]^{tk})$ 为满足引理 4.2 性质 (i)-(iii) 的 $tk$-图。由于 $F$ 包含一条 $tk$-边，其 $k$-阴影 $\sigma_k(F)$ 至少包含 $\binom{tk}{k} \geq 2$ 条边。因此引理 3.1 适用于 $J = \sigma_k(F)$，$e = 2t+2$，$\epsilon$ 替换为 $\epsilon/2$。它给出：对充分大的 $n$，存在近似最优的、导出的、$(2t+2)$-局部稀疏的 $\sigma_k(F)$-密铺 $P$。给定上述 $F$ 和 $P$，令 $H(\mathcal{F})$ 为构造 4.1 中定义的 $tk$-图。由引理 4.3，$H(\mathcal{F})$ 是 $(t+1)$-联集自由的。此外，(14) 表明 $|H(\mathcal{F})|$ 满足 (12) 中要求的下界。这完成了定理 1.1 中 $a = 0$ 情形的证明。 $\square$

引理 4.2 和引理 4.3 的证明推迟至下两个小节。

**4.1 引理 4.2 的证明**

我们按如下方式构造所需的 $tk$-图 $F$。设 $c = c(tk-1, k, 2t+2)$ 为应用引理 2.1（取 $r = tk-1$，$e = 2t+2$）所得常数。选取 $q_0 = q_0(t, k, \epsilon)$ 充分大，使得对每个 $q \geq q_0$，

$$\frac{\binom{q}{k}}{\left\lceil \frac{cq^{k+1}}{2t+1} \right\rceil} \leq \frac{\epsilon}{2} \binom{tk-1}{k-1}.$$

设 $m_0 = q_0 + \left\lceil \frac{cq_0^{k+1}}{2t+1} \right\rceil$，固定任意 $m \geq m_0$。令 $q$ 为满足 $q + \left\lceil \frac{cq^{k+1}}{2t+1} \right\rceil \geq m$ 的最小正整数，$N = m - q$。则 $q \geq q_0$。由 $q$ 的最小性，有

$$q - 1 + \left\lceil \frac{c(q-1)^{k+1}}{2t+1} \right\rceil < m,$$

从而 $\left\lceil \frac{c(q-1)^{k+1}}{2t+1} \right\rceil \leq N \leq \left\lceil \frac{cq^{k+1}}{2t+1} \right\rceil$。

设 $G \subseteq ([q]^{tk-1})$ 为由引理 2.1 得到的 $(tk-1)$-图。则 $G$ 至少有 $c q^{k+1} / (2t+1)$ 条边，且对任意 $2 \leq \ell \leq 2t+2$ 是 $(\ell(tk-1) - (\ell-1)k - 1, \ell)$-自由的。由于 $|G| \geq \left\lceil \frac{cq^{k+1}}{2t+1} \right\rceil \geq N$，我们可以从 $G$ 中选取 $N$ 条不同边 $G_1, \ldots, G_N$。引入一个新顶点集 $U = \{u_i : i \in [N]\}$，与 $[q]$ 不相交，并令 $[q] \cup U$ 与 $[m]$ 等同。定义

$$F = \{G_i \cup \{u_i\} : i \in [N]\} \subseteq ([m]^{tk}).$$

族 $F$ 是 $(t+1)$-联集自由的，事实上对每个 $s \geq 1$ 都是 $s$-联集自由的，因为私有顶点 $u_i$ 仅出现在边 $G_i \cup \{u_i\} \in F$ 中。因此并集中包含的私有顶点集恰好确定了 $F$ 中哪些边参与了该并集。

证明 (ii)：取任意 $I \subseteq [N]$ 满足 $|I| = \ell$，其中 $2 \leq \ell \leq 2t+2$。由于私有顶点各不相同且在 $[q]$ 之外，且 $G$ 是 $(\ell(tk-1) - (\ell-1)k - 1, \ell)$-自由的，有

$$\left|\bigcup_{i \in I} (G_i \cup \{u_i\})\right| = \left|\bigcup_{i \in I} G_i\right| + \ell \geq \ell(tk-1) - (\ell-1)k + \ell = \ell tk - (\ell-1)k.$$

这证明了 $F$ 对任意 $2 \leq \ell \leq 2t+2$ 是 $(\ell tk - (\ell-1)k - 1, \ell)$-自由的。

最后，$F$ 的 $k$-阴影由完全在基集 $[q]$ 中的 $k$-集以及包含一个私有顶点的 $k$-集组成。因此

$$|\sigma_k(F)| \leq \binom{q}{k} + |F| \binom{tk-1}{k-1}.$$

利用 $|F| = N$ 和 $q_0$ 的选取，得到

$$\frac{|F|}{|\sigma_k(F)|} \geq \frac{N}{\binom{q}{k} + N \binom{tk-1}{k-1}} = \frac{1}{\binom{q}{k}/N + \binom{tk-1}{k-1}} \geq \frac{1}{(1+\epsilon/2)\binom{tk-1}{k-1}} \geq (1-\epsilon/2) \binom{tk-1}{k-1}.$$

这证明了 (iii)，从而完成了引理证明。

**4.2 引理 4.3 的证明**

在给出引理 4.3 的证明之前，先陈述一个有用的命题。

**命题 4.4** 设 $F$ 为一个 $tk$-图，$P = \{(V(J_i), J_i) : i \in [|P|]\}$ 为一个导出的 $\sigma_k(F)$-密铺。设 $H(\mathcal{F})$ 如构造 4.1 中定义。则以下结论成立：

(i) 设 $F_i$ 和 $F_{i'}$ 为 $H(\mathcal{F})$ 中两个不同的 $F$ 的副本。

因此，对于每条边 F∈Fi，我们都有 |F∩V(Fi′)|≤k?1。(ii) 若 F 是 (2tk?k?1,2)-自由的，则对于 H(F) 中任意两条不同的边 F 和 F′，都有 |F∩F′|≤k。

证明：为证明 (i)，首先由构造 4.1 知 V(Fi)=V(Ji) 且 V(Fi′)=V(Ji′)。现在，若 |F∩V(Fi′)|≥k，则由构造可知，存在一个 k-元子集 T?F?V(Ji)，使得 T?V(Ji)∩V(Ji′)。由于 T∈(Fk)?σk(Fi)=Ji，这与 P 是诱导的假设矛盾。

(ii) 的证明分为两种情况。若 F 和 F′ 属于 F 的同一副本，则 F 的 (2tk?k?1,2)-自由性直接蕴含 |F∩F′|≤k。若 F 和 F′ 属于不同副本，例如 F∈Fi 且 F′∈Fi′，其中 i≠i′，则由 (i) 知 |F∩F′|≤|F∩V(Fi′)|≤k?1。无论哪种情况，所需的不等式都成立。□

现在我们能够证明引理 4.3。

引理 4.3 的证明：

我们首先证明对于所有 2≤?≤2t+2，H(F) 是 (??tk?(??1)k?1,?)-自由的。固定这样一个 ?，设 F1,…,F? 为 H(F) 中任意 ? 条不同的边。这些边属于 F 的若干不同副本 F1,…,Fs，其中 1≤s≤2t+2。对于每个 i∈[s]，设 Li?[?] 为那些满足 Fj∈Fi 的指标 j 组成的集合，并记 ?i=|Li|。注意到族 {Li:i∈[s]} 划分了 [?]，因此 ∑i=1s?i=?。

对于每个 i∈[s]，设 Xi=∪j∈LiV(Fj)。由于 Xi?V(Fi)，我们有 |?i=1sV(Fi)|≤|?i=1sXi|+∑i=1s|V(Fi)|?∑i=1s|Xi|。

利用引理 4.2(ii) 中 F 的自由性，对于每个 i∈[s]，我们有 |Xi|≥?i?tk?(?i?1)k（其中 ?i=1 的情况是平凡的）。利用 P 的局部稀疏性，我们还得到 |?i=1sV(Fi)|≥sm?(s?1)k（当 s=1 时同样是平凡的）。由于每个 Xi?V(Fi)，这两个不等式给出 |?i=1?Fi|=|?i=1sXi|≥∑i=1s|Xi|+|?i=1sV(Fi)|?∑i=1s|V(Fi)|≥∑i=1s?i?tk?(?i?1)k+sm?(s?1)k?sm=??tk?(??1)k，正如所需。

接下来，我们证明 H(F) 是 t-无覆盖的。假设存在 t+1 条不同的边 F1,…,Ft+1∈H(F) 使得 Ft+1?∪i=1tFi，这将导致矛盾。这意味着 (15) |?i=1t+1Fi|=|?i=1tFi|≤t?tk。若不等式 (15) 严格成立，则我们得到与 H(F) 的 ((t+1)?tk?tk?1,t+1)-自由性矛盾的结论。若等式成立，则 F1,…,Ft 两两不相交。此外，由论断 4.4(ii)，对于所有 i∈[t]，有 |Ft+1∩Fi|≤k。由于 Ft+1?∪i=1tFi，因此对于每个 i，有 |Ft+1∩Fi|=k。论断 4.4(i) 随后推出 F1,…,Ft+1 包含在 F 的同一副本中，这与 F 是 t-无覆盖的事实矛盾，而后者是由 F 是 (t+1)-无并的假设推出的。

最后，我们证明 H(F) 是 (t+1)-无并的。假设存在不同的子族 A,B?H(F)，满足 1≤|A|,|B|≤t+1，使得 ∪A∈AA=∪B∈BB。由于 H(F) 是 t-无覆盖的，我们有 |A|=|B|=t+1。不失一般性，设 A={C1,…,Cp,Ap+1,…,At+1}，B={C1,…,Cp,Bp+1,…,Bt+1}，其中 A∩B={C1,…,Cp}，且 0≤p≤t。设 X=∪i=1pCi，Y=∪i=p+1t+1Ai，Z=∪i=p+1t+1Bi。由 X∪Y=X∪Z，我们得到 (16) |X∪Y∪Z|=|X∪Y|=|X∪Z|≤(t+1)?tk。

注意到 A∪B 由 2t+2?p 条不同的边组成。应用 H(F) 的 ((2t+2?p)?tk?(2t+1?p)k?1,2t+2?p)-自由性，得到 (17) |X∪Y∪Z|≥(2t+2?p)?tk?(2t+1?p)k。结合上界 (16)，我们得到 (t+1)?tk≥(2t+2?p)?tk?(2t+1?p)k。化简此不等式得到 (t?1)/(t?1)≤p≤t。鉴于 p 是 0 到 t 之间的整数，唯一可行的情况是：(1) t≥2 且 p=t；(2) t=2 且 p=1。我们将分别处理这两种情况。

情况 (1)：t≥2 且 p=t。此时 Y=At+1 且 Z=Bt+1。由论断 4.4(ii)，设 |At+1∩Bt+1|=k?x，其中 x≥0。条件 YΔZ=At+1ΔBt+1?X 蕴含 |X∪At+1∪Bt+1|≤|X|+|At+1∩Bt+1|≤t?tk+k?x。由于 H(F) 是 ((t+2)?tk?(t+1)k?1,t+2)-自由的，我们还有 |X∪At+1∪Bt+1|≥(t+2)?tk?(t+1)k。结合上述两个不等式得到 (t+2)?tk?(t+1)k≤t?tk+k?x，这仅在 t=2 且 x=0 时成立。

此时 H(F) 是一个 2k-图，且我们有 C1∪C2∪A3=C1∪C2∪B3，其中 |A3∩B3|=k。由论断 4.4(i)，A3 和 B3 属于 F 的同一副本，记为 Fi。由于 Fi 是 3-无并的，C1 和 C2 中至少有一个不属于 Fi；设 C1?Fi。由论断 4.4(i)，得 |C1∩(A3ΔB3)|≤|C1∩V(Fi)|≤k?1。由于 A3ΔB3?X=C1∪C2 且 |A3ΔB3|=2k，我们有 |C2∩(A3ΔB3)|≥|A3ΔB3|?|C1∩(A3ΔB3)|≥2k?(k?1)=k+1。因此，|C2∪A3∪B3|≤|C2|+|A3∪B3|?|C2∩(A3ΔB3)|≤4k?1=3?2k?2k?1，这与 H(F) 的 (3?2k?2k?1,3)-自由性矛盾。

情况 (2)：t=2 且 p=1。此时有 C1∪A2∪A3=C1∪B2∪B3。由 (16)，我们有 |C1∪A2∪A3∪B2∪B3|≤6k。由于 H(F) 是 (5?2k?4k?1,5)-自由的，我们还有 |C1∪A2∪A3∪B2∪B3|≥5?2k?4k=6k。因此，|C1∪A2∪A3∪B2∪B3|=|C1∪A2∪A3|=|C1∪B2∪B3|=6k。由于 H(F) 是一个 2k-图，上述等式蕴含 C1,A2,A3 两两不相交，同样 C1,B2,B3 也两两不相交。这迫使 A2∪A3=B2∪B3。因此，|A2∪A3∪B2∪B3|=|A2∪A3|≤4k，这与 H(F) 的 (4?2k?3k?1,4)-自由性矛盾。

因此，H(F) 是 (t+1)-无并的。证毕。□

5. 结论与展望

我们已经确定了 Ut+1(n,r) 的渐近行为（至低阶项），对于几乎所有整数 t≥2 和 r≥3 成立。唯一未被覆盖的族是 {U3(n,2s?1), Us+1(n,s+1), Us+1(n,s+2): s≥2} 和 U4(n,7)。我们的工作留下了几个自然的开放问题。

例外情形。对于我们的构造不适用的参数，已知的下界和上界不匹配，在 n 的指数上留有空隙。确定这些 Ut+1(n,r) 的 Turán 指数或其不存在性是有趣的。与此相关，我们回顾 Füredi 和 Ruszinko [23] 证明了对于所有 r≥3，Ur(n,r)>n^{2-o(1)}，并猜想 Ur(n,r)=o(n^2)。如果他们的猜想为真，则 Ur(n,r) 没有 Turán 指数。

U2(n,r) 的情形。虽然我们的主定理没有为 U2(n,r) 提供精确的渐近界，但当 3 整除 r 时，我们可以改进下界。对于任意 k≥1，我们可以证明 U2(n,3k)≥(1?o(1)) \binom{n}{2k}/\binom{3k}{2k}，这改进了 Frankl 和 Füredi 长期以来的下界 U2(n,3k)≥1/\binom{3k}{k}\binom{3k}{2k}-o(1) n^{2k}（参见 [18, 命题 1.2 和定理 1.3]）。由于证明遵循与定理 1.1 类似的策略，我们省略了其细节。一个基本问题是退化 Turán 密度 lim_{n→∞} U2(n,r)/n^{\lceil 4r/3 \rceil/2} 是否存在。当 r=2 时，该问题化归为 Erd?s 的经典猜想 (1)。

确定性构造。我们的结果依赖于概率方法。寻找能够匹配这些渐近界的显式（确定性）构造的问题值得进一步研究。

刘苗 | 上官冲 | 张晨阳
山东大学数学与交叉科学研究中心，青岛，266237，中国