在最大度条件下广义三角形的正共度极值问题研究

Positive Codegree Andrásfai-Erdős-Sós Theorem for the Generalized Triangle under Max-Degree Constraints

摘要: 著名的Andrásfai-Erdős-Sós定理表明：任意一个n个顶点、最小度大于2n/5的三角形禁止图必为二部图。设$T_r=\left\{\left\{1,\cdots ,r-1,r\right\},\left\{1,\cdots ,r-1,r+1\right\},\left\{r,r+1,\cdots ,2r-1\right\}\right\}$ 为r-一致的广义三角形。在本文中，我们证明了：当$n$ 充分大时，若$\mathscr{H}$ 是一个含n个顶点的$T_r$ -禁止的r-一致超图，并且满足每一个$\left(r-1\right)$ -元组要么不包含于任何超边中，要么至少包含于超过$\frac{n}{r}-\frac{{\Delta }_{r-1}\left(\mathscr{H}\right)}{2r}$ 条超边中，则$\mathscr{H}$ 必为r-部超图。

Abstract: The celebrated Andrásfai-Erdős-Sós Theorem shows that every n-vertex triangle-free graph with minimum degree greater than 2n/5 must be bipartite. Denote the $T_r=\left\{\left\{1,\cdots ,r-1,r\right\},\left\{1,\cdots ,r-1,r+1\right\},\left\{r,r+1,\cdots ,2r-1\right\}\right\}$ r-uniform generalized triangle. In this paper, we prove the following strengthening of the above theorem: for sufficiently large n, if $\mathscr{H}$ is an n-vertex $T_r$ -free r-uniform hypergraph such that every $\left(r-1\right)$ -tuple of vertices is either contained in no hyperedge or in more than $\frac{n}{r}-\frac{{\Delta }_{r-1}\left(\mathscr{H}\right)}{2r}$ hyperedges, then $\mathscr{H}$ must be r-partite.

1. 引言

超图是在有限集合上定义的顶点和超边的集合，用$\mathscr{H}=\left(V\left(\mathscr{H}\right),E\left(\mathscr{H}\right)\right)$ 表示，其中，$V\left(\mathscr{H}\right)$ 表示顶点的集合，$E\left(\mathscr{H}\right)$ 表示超边的集合，$e\left(\mathscr{H}\right)$ 表示$\mathscr{H}$ 中的超边数。在图中一条边中只包含两个顶点，而在超图中，一条边可以包含多个顶点，称为超边。$k$ -一致超图是指超图中任意一条超边均恰好包含$k$ 个顶点，$k$ -一致超图也可以简称为$k$ -图。令$\mathscr{H}$ 是一个有$n$ 个顶点的$k$ -图，$\mathscr{H}$ 中点$u$ 的度是指包含$u$ 的超边数量，记为${\mathrm{deg}}_{\mathscr{H}}\left(u\right)$ 。超图的最小度$\delta \left(\mathscr{H}\right)$ 是指超图中任意一个顶点包含的最少的超边数量。超图的最大度$\Delta (\mathscr{H})$ 是指超图中某个顶点包含的最多的超边数量。给定一个$r$ -图族F，若一个$r$ -图$\mathscr{H}$ 不包含$F$ 的任何子图，则称$\mathscr{H}$ 是$F$ -禁止的。对任意$r\ge 2$ ，定义$r$ -一致广义三角形为$T_r=\left\{\left\{1,\cdots ,r-1,r\right\},\left\{1,\cdots ,r-1,r+1\right\},\left\{r,r+1,\cdots ,2r-1\right\}\right\}$ 。超图$\mathscr{H}$ 的影子(shadow) $\partial \mathscr{H}$ 定义为

$\partial \mathscr{H}:=\left\{e\in \left(\begin{array}{c}V\left(\mathscr{H}\right)\\ r-1\end{array}\right):存在E\in \mathscr{H}使得e\subseteq E\right\}。$

对于任意$e\in \partial \mathscr{H}$ ，其在$\mathscr{H}$ 中的邻居定义为$N_{\mathscr{H}}\left(e\right):=\left\{v\in V\left(\mathscr{H}\right):e\cup \left\{v\right\}\in \mathscr{H}\right\}。$

按照Balogh-Lemons-Palmer [1]的定义，$r$ -图$\mathscr{H}$ 的最小正共度${\delta }_{r-1}^{+}\left(\mathscr{H}\right)$ 定义为使得每一个$\left(r-1\right)$ -元子集要么不包含于任何超边中，要么至少包含于$k$ 条超边中的最大整数$k$ ，即

${\delta }_{r-1}^{+}\left(\mathscr{H}\right):=\min \left\{\left|N_{\mathscr{H}}\left(e\right)\right|:e\in \partial \mathscr{H}\right\}。$

我们定义$r$ -图$\mathscr{H}$ 的最大正共度${\Delta }_{r-1}\left(\mathscr{H}\right)$ 定义为存在$\left(r-1\right)$ -元子集要么不包含于任何超边中，要么至多包含于$k$ 条超边中的最大整数$k$ ，即

${\Delta }_{r-1}\left(\mathscr{H}\right):=\max \left\{\left|N_{\mathscr{H}}\left(e\right)\right|:存在e\in \partial \mathscr{H}\right\}。$

注意，当$r=2$ 且图中不存在孤立点时，最小正共度恰好等于最小度。在一篇经典的工作[2]中，Andrásfai、Erdős与Sós证明：当$\ell \ge 2$ 时，任意一个含$n$ 个顶点的，最小度大于$\frac{3\ell -4}{3\ell -1}n$ 的$K_{\ell +1}$ -禁止图必为$\ell$ -部图，且该界是紧的。该结果面向超图的推广在多项工作中已有研究(如[3]-[8])，但直到最近，针对3-一致广义三角形$T_3$ 的首个紧的结果才由[9]给出。

定理1.1 [9] 当$n\ge 5000$ ，任意一个含$n$ 个顶点、满足$\delta \left(\mathscr{H}\right)>\frac{4}{45}{n}^2$ 的$T_3$ -禁止的3-一致超图必为三部超图。

文献[10]研究$T_r$ 的Andrásfai-Erdős-Sós定理的最小正共度的推广：对于给定的$r$ ，最小的实数$x$ 使得任意一个$n$ 个顶点满足${\delta }_{r-1}^{+}\left(\mathscr{H}\right)>xn$ 的$T_r$ -禁止的$r$ -一致超图是多少？目前已知的唯一紧的情形是图论中的原始的Andrásfai-Erdős-Sós定理，即任意一个$n$ 个顶点、最小度大于$2n/5$ 的三角形禁止图必为二部图。下面的定理给出了所有$r\ge 3$ 的精确答案。

定理1.2 [10] 当$n\ge \frac{\left(r-1\right)\left(2r+1\right)}{2}$ 时，任意一个含$n$ 个顶点$T_r$ -禁止的$r$ -一致超图$\mathscr{H}$ 满足

${\delta }_{r-1}^{+}\left(\mathscr{H}\right)>\frac{2n}{2r+1}$ ，

则$\mathscr{H}$ 必为$r$ -部超图。

在本文中，我们建立了上述定理的一个强化版本：

定理1.3 当$n\ge r\left(r-1\right)+\frac{1}{2}{\Delta }_{r-1}\left(\mathscr{H}\right)$ ，若$\mathscr{H}$ 是一个含$n$ 个顶点$T_r$ -禁止的$r$ -一致超图，并且满足

${\delta }_{r-1}^{+}\left(\mathscr{H}\right)>\frac{n}{r}-\frac{1}{2r}{\Delta }_{r-1}\left(\mathscr{H}\right)$ ，

则$\mathscr{H}$ 必为$r$ -部超图。

定理1.3中的不等式界${\delta }_{r-1}^{+}\left(\mathscr{H}\right)>\frac{n}{r}-\frac{1}{2r}{\Delta }_{r-1}\left(\mathscr{H}\right)$ 是最优的，这一点可由下面的构造加以说明。设$W_5^r$ 为一个$r$ -一致的5-轮(5-wheel)超图，其顶点数为$r+3$ ，包含5条超边。具体而言，其超边集合为$\left\{u_1,\cdots ,u_{r-2},v_1,v_2\right\},\left\{u_1,\cdots ,u_{r-2},v_2,v_3\right\},\left\{u_1,\cdots ,u_{r-2},v_3,v_4\right\},\left\{u_1,\cdots ,u_{r-2},v_4,v_5\right\},\left\{u_1,\cdots ,u_{r-2},v_5,v_1\right\}$ 。

给定一个正整数向量$\left\{x_1,x_2,x_3,x_4,x_5,y_1,y_2,\cdots ,y_{r-2}\right\}$ ，其中

$\left\{x_1,x_2,x_3,x_4,x_5\right\}=\left\{\frac{n}{2r+1}+\frac{\alpha }{2}n,\frac{n}{2r+1}-\frac{3}{4}\alpha n-\frac{1}{2}\beta n,\frac{n}{2r+1}-\frac{3}{4}\alpha n-\frac{1}{2}\beta n,\frac{n}{2r+1}+\frac{\alpha }{2}n,\frac{n}{2r+1}+\frac{\alpha }{2}n\right\}$ ，

$\left\{y_1,y_2,\cdots ,y_{r-2}\right\}=\left\{\frac{2n}{2r+1}+\frac{\beta }{r-2}n,\frac{2n}{2r+1}+\frac{\beta }{r-2}n,\cdots ,\frac{2n}{2r+1}+\frac{\beta }{r-2}n\right\}$ ，

其中$\alpha =\frac{{\Delta }_{r-1}\left(\mathscr{H}\right)}{n}-\frac{2}{2r+1}$ ，$\beta =\frac{r-2}{r\left(2r+1\right)}-\frac{r-2}{2rn}{\Delta }_{r-1}\left(\mathscr{H}\right)$ 。

通过将每个顶点$u_i$ 替换为大小为$y_i$ 的点集、每个顶点$v_j$ 替换为大小为$x_j$ 的点集，并将每一条超边替换为相应的完全$r$ -部$r$ -一致超图，可以得到$W_5^r$ 的一个膨胀(blow-up)，记为

$W_5^r\left[x_1,x_2,x_3,x_4,x_5,y_1,y_2,\cdots ,y_{r-2}\right]$ 。

容易验证，$W_5^r$ 的任意膨胀都是$T_r$ -禁止的，但并非$r$ -部超图。另外通过直接计算可以验证，超图$\mathcal{G}:=W_5^r\left[x_1,x_2,x_3,x_4,x_5,y_1,y_2,\cdots ,y_{r-2}\right]$ 恰有$n$ 个顶点且其最小正共度满足${\delta }_{r-1}^{+}\left(\mathscr{H}\right)=\frac{n}{r}-\frac{1}{2r}{\Delta }_{r-1}\left(\mathscr{H}\right)$ 。

因此，定理1.3中关于正共度的阈值条件在一般情形下是不可改进的。容易验证，定理1.3是对$T_r$ 的Andrásfai-Erdős-Sós定理的最小正共度的推广。

接下来，我们将在第2节中给出定理1.3的完整证明。

2. 定理1.3的证明

本节我们给出定理1.3的完整证明。首先回顾一些必要的定义和预备结果。

令$\mathscr{H}$ 是一个3-一致超图。对于任意一个$u\in V\left(\mathscr{H}\right)$ ，我们定义$L_{\mathscr{H}}\left(u\right):=\left\{e\in \left(\begin{array}{c}V\left(\mathscr{H}\right)\\ 2\end{array}\right):e\cup \left\{u\right\}\in E\left(\mathscr{H}\right)\right\}$ 。对于任意$e\in \partial \mathscr{H}$ ，其领域定义为$N_{\mathscr{H}}\left(e\right):=\left\{v\in V\left(\mathscr{H}\right):e\cup \left\{v\right\}\in \mathscr{H}\right\}$ ，在$\mathscr{H}$ 中一个点$v\in V\left(\mathscr{H}\right)$ 的领域被定义为$N_{\mathscr{H}}\left(v\right):=\left\{u\in V\left(\mathscr{H}\right)\text{}\left\{v\right\}:存在e\in \mathscr{H}使得\left\{u,v\right\}\subseteq e\right\}$ 。由定义可以直接验证，对任意顶点$v\in V\left(\mathscr{H}\right)$ ，有

$\underset{e\in \partial \mathscr{H}:v\in e}{\cup }{N}_{\mathscr{H}}\left(e\right)=N_{\mathscr{H}}\left(v\right)$ (1)

对任意整数$r\ge 2$ ，记${\Sigma }_r$ 为如下$r$ -一致超图的集合：其包含三条超边$A$ ，$B$ ，$C$ ，满足$\left|A\cap B\right|=r-1$ 且对称差$A\Delta B\subseteq C$ ，注意到$T_r\in {\Sigma }_r$ 。

命题2.1：设$r\ge 3$ 。若$\mathscr{H}$ 是一个$T_r$ -禁止的$r$ -一致超图，并且${\delta }_{r-1}^{+}\left(\mathscr{H}\right)\ge r$ ，则$\mathscr{H}$ 也是${\Sigma }_r$ -禁止的。

证明：设$\mathscr{H}$ 是一个满足条件的$T_r$ -禁止的$r$ -图。反证法假设存在三条超边$A,B,C\in E\left(\mathscr{H}\right)$ ，使得$\left|A\cap B\right|=r-1$ ，且$A\Delta B\subseteq C$ 。不妨设$A=\left\{u_1,\cdots ,u_{r-1},u_r\right\}$ ，$B=\left\{u_1,\cdots ,u_{r-1},u_{r+1}\right\}$ ，在所有满足条件的超边$C$ 中，选取一条使得$\left|C\cap \left\{u_1,\cdots ,u_{r-1}\right\}\right|$ 最小，则$\left\{\left\{u_1,\cdots ,u_{r-1},u_r\right\},\left\{u_1,\cdots ,u_{r-1},u_{r+1}\right\},C\right\}$ 构成$\mathscr{H}$ 中的一个$T_r$ ，与$\mathscr{H}$ 是$T_r$ -禁止的矛盾。因此必有$\left|C\cap \left\{u_1,\cdots ,u_{r-1}\right\}\right|\ge 1$ ，不失一般性，可设$C\cap \left\{u_1,\cdots ,u_{r-1}\right\}=\left\{u_1,\cdots ,u_{i*}\right\}$ ，其中$i*\in \left[r-2\right]$ 。令$e:=C\backslash \left\{u_1\right\}$ ，则$e\in \partial \mathscr{H}$ 。由于${\delta }_{r-1}^{+}\left(\mathscr{H}\right)\ge r$ ，所以存在某个顶点$\omega \in V\left(\mathscr{H}\right)\backslash \left\{u_1,\cdots ,u_{r-1}\right\}$ 使得$C^{\prime }:=e\cup \left\{\omega \right\}\in \mathscr{H}$ 。注意到$\left\{u_r,u_{r+1}\right\}\subseteq C^{\prime }$ ，并且$\left|C^{\prime }\cap \left\{u_1,\cdots ,u_{r-1}\right\}\right|<\left|C\cap \left\{u_1,\cdots ,u_{r-1}\right\}\right|$ ，这与$C$ 的极小性假设相矛盾。命题得证。

我们称集合$I\subseteq V\left(\mathscr{H}\right)$ 在$\mathscr{H}$ 中是独立集，如果$\mathscr{H}$ 的任意一条超边至多包含$I$ 中的一个顶点。

引理2.2：设$\mathscr{H}$ 为一个$T_r$ -禁止的$r$ -一致超图，且$E=\left\{u_1,\cdots ,u_r\right\}\in \mathscr{H}$ 是一条超边。若${\delta }_{r-1}^{+}\left(\mathscr{H}\right)\ge r$ ，则对任意$i\in \left[r\right]$ ，有

$N_{\mathscr{H}}\left(E\text{}\left\{u_i\right\}\right)\cap N_{\mathscr{H}}\left(u_i\right)=\varnothing 。$ (2)

此外，集合$\left\{N_{\mathscr{H}}\left(E\text{}\left\{u_i\right\}\right):i\in \left[r\right]\right\}$ 两两不交，且均为独立集。

证明：由于对称性，只需证明$i=r$ 的情形。反证法假设存在顶点$u_{r+1}\in N_{\mathscr{H}}\left(E\text{}\left\{u_r\right\}\right)\cap N_{\mathscr{H}}\left(u_r\right)$ 。

由$u_{r+1}\in N_{\mathscr{H}}\left(u_r\right)$ ，存在一条包含$\left|\left\{u_r,u_{r+1}\right\}\right|$ 的超边$E^{\prime }\in \mathscr{H}$ 。注意到$\left\{E,\left\{u_1,\cdots ,u_{r-1},u_{r+1}\right\},E^{\prime }\right\}$ 构成${\Sigma }_r$ 中的一个元素，这与命题2.1矛盾，从而得到(2)。由(2)立刻推出集合$N_{\mathscr{H}}\left(E\text{}\left\{u_i\right\}\right)$ 两两不交。若其中某个集合不是独立集，我们可以假设这里存在两个不同的点$v,w\in N_{\mathscr{H}}\left(E\text{}\left\{u_r\right\}\right)\cap e$ 其中$e\in \mathscr{H}$ 。注意到$\left\{\left(E\text{}\left\{u_r\right\}\right)\cup \left\{v\right\},\left(E\text{}\left\{u_r\right\}\right)\cup \left\{w\right\},e\right\}$ 是${\Sigma }_r$ ，再次与命题2.1矛盾。

下面开始证明定理1.3本身。

定理1.3的证明：设$n\ge r\left(r-1\right)+\frac{1}{2}{\Delta }_{r-1}\left(\mathscr{H}\right)$ 且$\mathscr{H}$ 是一个含$n$ 个顶点的$T_r$ -禁止的$r$ -一致超图，满足${\delta }_{r-1}^{+}\left(\mathscr{H}\right)>\frac{n}{r}-\frac{1}{2r}{\Delta }_{r-1}\left(\mathscr{H}\right)$ ，显然有${\delta }_{r-1}^{+}\left(\mathscr{H}\right)\ge r$ ，记$V:=V\left(\mathscr{H}\right)$ 。

断言2.3：存在$r$ 个两两不交的独立集$V_1,\cdots ,V_r\subseteq V$ 使得

$\left|V_1\right|>{\Delta }_{r-1}\left(\mathscr{H}\right),\left|V_2\right|>\frac{n}{r}-\frac{1}{2r}{\Delta }_{r-1}\left(\mathscr{H}\right),\cdots ,\left|V_r\right|>\frac{n}{r}-\frac{1}{2r}{\Delta }_{r-1}\left(\mathscr{H}\right)$ 。 (3)

证明：固定一条包含最大正共度的边$E=\left\{u_1,\cdots ,u_r\right\}\in \mathscr{H}$ ，对每个$i\in \left[r\right]$ ，定义$V_i:=N_{\mathscr{H}}\left(E\text{}\left\{u_i\right\}\right)$ 。不失一般性假设$N_{\mathscr{H}}\left(E\text{}\left\{u_1\right\}\right)={\Delta }_{r-1}\left(\mathscr{H}\right)$ 。由引理2.2可知，这些集合两两不交且均为独立集。再由

${\delta }_{r-1}^{+}\left(\mathscr{H}\right)>\frac{n}{r}-\frac{1}{2r}{\Delta }_{r-1}\left(\mathscr{H}\right)$ 且可得(3)成立。

令$V_1,\cdots ,V_r$ 为满足(3)的极大独立集族，并设$Z:=V\text{}\left(V_1\cup \cdots \cup V_r\right)$ 。由极大性可得，对任意$z\in Z$ 和任意$i\in \left[r\right]$ ，集合$V_i\cup \left\{z\right\}$ 不是独立集。注意到

$\left|Z\right|\le n-{\Delta }_{r-1}\left(\mathscr{H}\right)-\left(r-1\right){\delta }_{r-1}^{+}\left(\mathscr{H}\right)<\frac{n}{r}-\frac{r+1}{2r}{\Delta }_{r-1}\left(\mathscr{H}\right)$ 。 (4)

若$Z=\varnothing$ ，则$\mathscr{H}$ 显然为$r$ -部超图。以下假设$Z\ne \varnothing$ ，并固定一个顶点$z_0\in Z$ 。设$R:=N_{\mathscr{H}}\left(z_0\right)$ 。对每个$i\in \left[r\right]$ ，定义$L_i:=\left\{e\in L_{\mathscr{H}}\left(z_0\right):\left|e\cap V_j\right|=1对所有j\in \left[r\right]\text{}\left\{i\right\}\right\}$ ，$N_i:=R\cap V_i$ 。由$V_1,\cdots ,V_r$ 的极大性可知，对每个$i\in \left[r\right]$ ，都有$N_i\ne \varnothing$ 。

断言2.4：$\left|R\right|>\left(r-1\right){\delta }_{r-1}^{+}\left(\mathscr{H}\right)$ 。

证明：固定一条边$\left\{v_1,\cdots ,v_{r-1}\right\}\in L_{\mathscr{H}}\left(z_0\right)$ 。对每个$i\in \left[r-1\right]$ ，令$e_i:=\left\{v_1,\cdots ,v_{r-1},z_0\right\}\text{}\left\{v_i\right\}$ ，$U_i:=N_{\mathscr{H}}\left(e_i\right)$ 。

由(1)可知$U_i\subseteq R$ 。再由引理2.2及${\delta }_{r-1}^{+}\left(\mathscr{H}\right)>\frac{n}{r}-\frac{1}{2r}{\Delta }_{r-1}\left(\mathscr{H}\right)$ 可得

$\left|R\right|\ge \left|U_1\right|+\cdots +\left|U_{r-1}\right|>\left(r-1\right){\delta }_{r-1}^{+}\left(\mathscr{H}\right)$

断言得证。

断言2.5：集合$\left\{L_1,\cdots ,L_r\right\}$ 中至多有一个是非空的。

证明：反证法假设集合$\left\{L_1,\cdots ,L_r\right\}$ 中至少有两个是非空的。由对称性，不妨设$L_1\ne \varnothing$ 且$L_r\ne \varnothing$ 。固定$\left\{v_1,\cdots ,v_{r-1}\right\}\in L_r$ ，$\left\{w_2,\cdots ,w_r\right\}\in L_1$ ，并假设$\left(v_1,\cdots ,v_{r-1}\right)\in V_1\times \cdots \times V_{r-1}$ ，$\left(w_2,\cdots ,w_r\right)\in V_2\times \cdots \times V_r$ (允许对某些$i\in \left[2,r-1\right]$ 有$v_i=w_i$ )。令$N_v:=N_{\mathscr{H}}\left(\left\{v_1,\cdots ,v_{r-1}\right\}\right)$ ，$N_w:=N_{\mathscr{H}}\left(\left\{w_2,\cdots ,w_r\right\}\right)$ 。

由于$V_1,\cdots ,V_r$ 在$\mathscr{H}$ 中是独立集，我们有

$N_v\subseteq V_r\cup Z,N_w\subseteq V_1\cup Z$ 。 (5)

由于$\left\{v_1,\cdots ,v_{r-1}\right\}，\left\{w_2,\cdots ,w_r\right\}\in L_{\mathscr{H}}\left(z_0\right)$ ，由式(2)得$R\cap N_v=R\cap N_w=\varnothing$ 。

这与式(5)、命题2.4以及假设${\delta }_{r-1}^{+}\left(\mathscr{H}\right)>\frac{n}{r}-\frac{1}{2r}{\Delta }_{r-1}\left(\mathscr{H}\right)$ 结合，我们得到

$\begin{array}{c}\left|R\cup N_v\cup N_w\right|=\left|R\right|+\left|N_v\right|+\left|N_w\right|-\left|N_v\cap N_w\right|\\ >\left(r-1\right){\delta }_{r-1}^{+}\left(\mathscr{H}\right)+2{\delta }_{r-1}^{+}\left(\mathscr{H}\right)-\left|Z\right|。\end{array}$

由(4)以及${\delta }_{r-1}^{+}\left(\mathscr{H}\right)>\frac{n}{r}-\frac{1}{2r}{\Delta }_{r-1}\left(\mathscr{H}\right)$ ，我们推断出

$\left|R\cup N_v\cup N_w\right|>\left(r+1\right){\delta }_{r-1}^{+}\left(\mathscr{H}\right)-\frac{n}{r}+\frac{r+1}{2r}{\Delta }_{r-1}\left(\mathscr{H}\right)=n。$

这与$\left|R\cup N_v\cup N_w\right|<n$ 矛盾。断言得证。

由对称性，我们可以假设对于任意$i\in \left[2,r\right]$ 有$L_i=\varnothing$ 。固定点$v_1\in N_1$ 。

断言2.6. 存在一条包含$\left\{z_0,v_1\right\}$ 的边$E\in \mathscr{H}$ ，使得$\left|E\cap \left(V_2\cup \cdots \cup V_r\right)\right|\ge r-2$ 。

证明：由于$v_1\in N_1$ ，在$\mathscr{H}$ 中存在一条包含$\left\{z_0,v_1\right\}$ 的边。在所有包含$\left\{z_0,v_1\right\}$ 的边中，选取一条$E$ ，使得$\left|E\cap \left(V_2\cup \cdots \cup V_r\right)\right|$ 最大。反证法假设$\left|E\cap \left(V_2\cup \cdots \cup V_r\right)\right|\le r-3$ 。

由于$V_1,\cdots ,V_r$ 在$\mathscr{H}$ 中是独立集，对每个$i\in \left[r\right]$ ，都有$\left|E\cap V_i\right|\le 1$ 。特别地，$\left|E\cap V_1\right|=\left\{v_1\right\}$ 。根据对称性，不妨设对某个$1\le i*\le r-2$ ，对所有$j\in \left[i*\right]$ ，都有$\left|E\cap V_j\right|\ne \varnothing$ 。记$v_j$ 为$E\cap V_j$ 中的顶点($j=1,\cdots ,i*$ )。由于$i*\le r-2$ ，有$\left|E\cap Z\right|\ge 2$ 。设$\left(E\text{}\left\{z_0\right\}\right)\cap Z=\left\{z_{i*+1},\cdots ,z_{r-1}\right\}$ ，令$e:=\left\{z_0,v_1,\cdots ,v_{i*},z_{i*+1},\cdots ,z_{r-2}\right\}$ 。由

${\delta }_{r-1}^{+}\left(\mathscr{H}\right)>\frac{n}{r}-\frac{1}{2r}{\Delta }_{r-1}\left(\mathscr{H}\right)$ 以及式(4)，得到

$\left|N_{\mathscr{H}}\left(e\right)\right|>\frac{n}{r}-\frac{1}{2r}{\Delta }_{r-1}\left(\mathscr{H}\right)>\frac{n}{r}-\frac{r+1}{2r}{\Delta }_{r-1}\left(\mathscr{H}\right)>\left|Z\right|$ 。

注意到$V_1,\cdots ,V_r$ 在$\mathscr{H}$ 中是独立集且对所有$j\in \left[i^{*}\right]$ ，都有$e\cap V_j\ne \varnothing$ 。因此存在$w\in V_{i*+1}\cup \cdots \cup V_r$ 使得$E^{\prime }:=e\cup \left\{w\right\}=\left\{z_0,v_1,\cdots ,v_{i*},w,z_{i*+1},\cdots ,z_{r-2}\right\}\in \mathscr{H}$ 。然而，$E^{\prime }$ 包含$\left\{z_0,v_1\right\}$ ，并且满足$\left|E^{\prime }\cap \left(V_2\cup \cdots \cup V_r\right)\right|=\left|\left(e\cup \left\{w\right\}\right)\cap \left(V_2\cup \cdots \cup V_r\right)\right|=\left|e\cap \left(V_2\cup \cdots \cup V_r\right)\right|+1=\left|E\cap \left(V_2\cup \cdots \cup V_r\right)\right|+1$ 。

因此，我们找到了$E^{\prime }$ 包含$\left\{z_0,v_1\right\}$ 且$\left|E^{\prime }\cap \left(V_2\cup \cdots \cup V_r\right)\right|>\left|E\cap \left(V_2\cup \cdots \cup V_r\right)\right|$ ，这与最开始的$\left|E\cap \left(V_2\cup \cdots \cup V_r\right)\right|$ 是最大的假设矛盾。命题得证。

由断言2.6可知，存在某个$j\in \left[2,r\right]$ 使得$L_j\ne \varnothing$ ，这与我们假设对所有$i\in \left[2,r\right]$ 都有$L_i=\varnothing$ 相矛盾。因此，定理1.2的证明完成。

3. 结论

在著名的Andrásfai-Erdős-Sós定理的基础上，文献[10]建立了在超图上的一个正共度(positive codegree)的推广。在本文中，我们按照Balogh-Lemons-Palmer [1]对$r$ -图$\mathscr{H}$ 的最小正共度${\delta }_{r-1}^{+}\left(\mathscr{H}\right)$ 的定义，定义了其最大正共度${\Delta }_{r-1}\left(\mathscr{H}\right)$ ，并做了一个加强的版本：当$n$ 充分大时，若$\mathscr{H}$ 是一个含$n$ 个顶点的$T_r$ -禁止的$r$ -一致超图，并且满足每一个$\left(r-1\right)$ -元组要么不包含于任何超边中，要么至少包含于超过$\frac{n}{r}-\frac{{\Delta }_{r-1}\left(\mathscr{H}\right)}{2r}$ 条超边中，则$\mathscr{H}$ 必为$r$ -部超图。在本文我们回到基本的极值问题，相较于文献[10]中的假设，本文通过引入最大共度参数，使附加条件更弱。这种对条件的弱化处理，不仅扩展了极值图的存在空间，而且显著提升了所得图结构的稳定性，使其在参数扰动下仍能保持良好的极值特性。另外，我们的极值构造表明，定理中关于正共度的阈值条件是紧的。我们希望这能激发对最大正共度顶点的存在如何影响极值问题更广泛的关注。例如，一个自然的想法是在定理1.3的基础上，研究[11]-[13]的结果在附加最大度约束下的情况。

NOTES

^*通讯作者。