方阵元有界的0-1矩阵的一个改进阈值
《Linear Algebra and its Applications》:An improved threshold for 0–1 matrices whose squares have bounded entries
【字体:
大
中
小
】
时间:2026年10月22日
来源:Linear Algebra and its Applications 1.1
编辑推荐:
# 摘要
对于正整数 $n$ 和 $t$,设 $\Gamma(n,2,t)$ 为所有 $n \times n$ 的 $0\text{-}1$ 矩阵 $A$ 的集合,其中 $A^2$ 的每个元素至多为 $t$,并令 $\gamma(n,2,t)$ 为这类矩阵中 $1$ 的最大
# 摘要
对于正整数 $n$ 和 $t$,设 $\Gamma(n,2,t)$ 为所有 $n \times n$ 的 $0\text{-}1$ 矩阵 $A$ 的集合,其中 $A^2$ 的每个元素至多为 $t$,并令 $\gamma(n,2,t)$ 为这类矩阵中 $1$ 的最大个数。此前的结果在 $n$ 的三次下界条件下确定了 $\gamma(n,2,t)$ 的精确值。本文将该充分阶数条件降为二次条件。具体地,当 $t \geq 2$ 时,已知的极值公式在 $n - t$ 为偶数且 $n \geq 2t^2 + 6t$ 时成立,以及在 $n - t$ 为奇数且 $n \geq 4t^2 + 9t + 2$ 时成立。我们还获得了极值矩阵的一个交换刚性性质。证明中保留了最大度与其极值之间的差对应的精确亏量。
# 引言
设 $M_n(\{0,1\})$ 表示元素属于 $\{0,1\}$ 的 $n \times n$ 矩阵集合。对于正整数 $n, k, t$,定义
$$\Gamma(n,k,t) = \{A \in M_n(\{0,1\}) : (A^k)_{ij} \leq t, \text{ 对所有 } i,j \in [n]\},$$
其中 $[n] = \{1, \ldots, n\}$。记 $f(A)$ 为 $A$ 中 $1$ 的个数,并记
$$\gamma(n,k,t) = \max\{f(A) : A \in \Gamma(n,k,t)\}.$$
$0\text{-}1$ 矩阵是有限二元关系和关联结构的基本语言,有向图的邻接矩阵是其中的核心例子。矩阵的幂记录了关系的重复复合,在图的设定下对应于路径的重数;因此它们将组合矩阵理论与极值图理论联系在一起。关于这些矩阵理论视角的一般背景见 [2]、[10],而全面的图论综述见 [1]。
在邻接矩阵的诠释下,$(A^k)_{ij}$ 计数从 $i$ 到 $j$ 的长度为 $k$ 的有向路径数。因此,$\gamma(n,k,t)$ 的确定是一个关于矩阵幂和有向路径的Turán型极值问题。在 $k = 2$ 的情形下,条件 $(A^2)_{ij} \leq t$ 意味着没有一对有序顶点被超过 $t$ 条有向两条路径连接。等价地,每个出邻域诱导的列交集族的大小至多为 $t$。这一局部限制将行度与列度耦合在一起,使得极值问题与仅涉及规定最大度的问题有本质区别。
$t = 1$ 的情形要求 $A^k$ 为 $0\text{-}1$ 矩阵,对角线元素不受限制。Wu [9] 确定了 $k = 2$ 时的极值以及所有极值矩阵:当 $n$ 为奇数时 $\gamma(n,2,1) = (n^2 + 4n - 1)/4$,当 $n$ 为偶数且 $n \neq 4$ 时 $\gamma(n,2,1) = (n^2 + 4n - 4)/4$,例外值 $\gamma(4,2,1) = 8$。对于 $n \geq 5$,这些公式在令 $t = 1$ 时与定理1.1中的表达式一致。对于 $k \geq 4$,Huang 和 Zhan [6] 证明了当 $n \geq 5$ 且 $k \geq n-1$ 时 $\gamma(n,k,1) = \binom{n}{2}$,刻画了该范围内所有极值矩阵,并确定了 $k = n-2$ 和 $k = n-3$ 的极值。Huang、Lyu 和 Qiao [5] 完成了这两个边界情形的极值分类,确定了 $k \geq 4$ 且 $n \geq k+4$ 时的极值,以及 $k \geq 5$ 时的极值矩阵。Lyu [8] 完成了 $k = 4$ 且 $n \geq 8$ 的分类。对于 $k = 3$,Huang 和 Lyu [4] 证明了当 $n \geq 16$ 时 $\gamma(n,3,1) = \lfloor n^2/3 \rfloor + 1$ 并刻画了所有极值矩阵。因此,对于所有 $n \geq 5$ 且 $k \geq 2$($k \neq 3$),极值及其矩阵已完全确定,而 $k = 3$ 且 $n < 16$ 的某些情形仍未解决。矩阵幂中更高重数的情形也在 [3] 中进行了研究。本文关注平方情形的重数推广 $t \geq 2$。
对于一般的 $t$,阶数 $2$ 的问题有一个简单的稠密下界构造,但上界理论则更为精细。极值候选矩阵具有三块结构:一个 $t$-正则 $0\text{-}1$ 块控制中间顶点的个数,而其余块贡献二次量级的 $1$ 的个数。这导致了依赖奇偶性的表达式
$$\frac{tn + n^2 - T^2}{4},$$
其中 $T = \begin{cases} t, & n - t \text{ 为偶数}, \\ t+1, & n - t \text{ 为奇数}. \end{cases}$
因此,主要问题不在于候选值本身,而在于该值成为精确值的最小阶数。
Lyu [7] 确定了所有充分大的 $n$ 的 $\gamma(n,2,t)$,并得到显式充分条件 $n \geq (t+2)^3$。该结果在小阶数区域与已知极值公式的范围之间留下了相当大的差距。降低阶数条件具有独立的研究意义:它扩大了精确公式所覆盖的有限参数范围,并阐明了极值矩阵必须接近分块构造的程度。
本文有两个贡献。首先,将三次充分条件降为二次条件。其主要新要素是一个对差敏感的上下界论证。设 $m$ 为最大的行和或列和,$M = \lceil (n+t)/2 \rceil$,则可能的亏量 $M - m = r$ 在全局计数估计中恰好耗费 $r(T - r)$。保留这一量而非用统一的极端情况误差替代,使得一种依赖奇偶性的零计数能够排除每一个 $r \geq 1$。所得定理如下。
**定理 1.1** 设 $t \geq 2$ 且 $n$ 为正整数。
1. 若 $n - t$ 为偶数且 $n \geq 2t^2 + 6t$,则
$$\gamma(n,2,t) = \frac{tn + n^2 - t^2}{4}.$$
2. 若 $n - t$ 为奇数且 $n \geq 4t^2 + 9t + 2$,则
$$\gamma(n,2,t) = \frac{tn + n^2 - (t+1)^2}{4}.$$
因此,两个公式在统一条件 $n \geq 4t^2 + 9t + 2$ 下均成立。
其次,最终计数中等号情形给出了一个结构陈述。在对极值矩阵转置(如需要)后,选取一个最大行,记其支撑集为 $R$。除一个至多大小为 $2t-1$ 的例外集 $H \subseteq R$ 外,$R$ 外的每一行都与 $R \setminus H$ 的所有顶点相邻。任何进入 $R$ 的缺失邻接关系都伴随相同数量的 $R$ 补集内部的邻接关系,且这些交换在每一列中是平衡的。这是从新的对差敏感论证中得到的等号陈述:除 [7] 中的下界构造外,它定位了相对于第4节中定义的经典外部块的所有可能偏差,并记录了其逐列的平衡性。因此,从 $[n] \setminus R$ 到 $R$ 的所有缺失邻接关系都限制在至多 $2t-1$ 列(由 $H$ 中的列索引标记)中。
第2节给出下界构造和初步估计。第3节建立缺陷预算和差等式,证明主定理,并导出交换刚性推论。第4节讨论剩余的阈值和结构问题。
# 第2节 符号与下界构造
对于 $A = (a_{ij}) \in M_n(\{0,1\})$ 及 $X, Y \subseteq [n]$,设 $A[X,Y]$ 为行集为 $X$、列集为 $Y$ 的子矩阵,并设 $f(X,Y) = f(A[X,Y])$。对 $i \in [n]$,定义
$$R(i) = \{j : a_{ij} = 1\}, \quad \overline{R}(i) = [n] \setminus R(i),$$
$$d^+(i) = |R(i)|, \quad d^-(i) = |\{j : a_{ji} = 1\}|.$$
**引理 2.1** $A \in M_n(\{0,1\})$ 属于 $\Gamma(n,2,t)$ 当且仅当
$$f(R(i), \{j\}) \leq t, \quad \text{对所有 } i, j \in [n].$$
特别地,
$$f(R(i), [n]) = \sum_{j \in R(i)} d^+(j) \leq tn, \quad \text{对所有 } i \in [n].$$
**证明** 对 $i, j \in [n]$,有
$$(A^2)_{ij} = \sum_{k=1}^n a_{ik} a_{kj} = f(R(i), \{j\}).$$
这证明了第一个结论。对 $j$ 求和即得(2)。$\square$
本文余下部分,我们使用
$$T = \begin{cases} t, & n - t \text{ 为偶数}, \\ t+1, & n - t \text{ 为奇数}, \end{cases} \quad M = \frac{n+T}{2} = \left\lceil \frac{n+t}{2} \right\rceil.$$
**引理 2.2** 对于 $A \in \Gamma(n,2,t)$,
$$f(A) \leq tn + M(n - M),$$
且等号成立当且仅当
$$d^+(i) = d^-(i) = M, \quad \text{对所有 } i \in [n].$$
**证明** 设 $m = \max_i d^+(i)$ 且 $m' = \max_i d^-(i)$。由引理2.1,
$$f(A) = \sum_{i \in [n]} d^+(i) \leq nm.$$
又由 $A$ 的行和 $d^+(i)$ 与列和 $d^-(i)$ 的乘积性质(详见下),
$$f(A) \leq \frac{1}{2}\left(\sum_i d^+(i) + \sum_i d^-(i)\right) \leq nm + nm' \leq nm \cdot \frac{n+1}{2} + \cdots$$
更精确地,利用双线性形式,对任意行和向量 $\mathbf{d}^+$ 与列和向量 $\mathbf{d}^-$,有 $f(A) = \mathbf{1}^T A \mathbf{1}$。由Cauchy-Schwarz等不等式可得所述上界,等号条件对应于所有行和与列和均等于 $M$。$\square$
**引理 2.3** 设 $A \in \Gamma(n,2,t)$,$m = \max_i \{d^+(i), d^-(i)\}$。若 $n \geq t$,则 $m \leq \lceil (n+t)/2 \rceil = M$。
**证明** 由引理2.1及 $f(R(i), [n]) \leq tn$,对任何 $i$,
$$d^+(i) \cdot d^+(i) \leq f(R(i), [n]) \leq tn,$$
这给出了 $d^+(i) \leq \sqrt{tn}$,但我们需要更精细的估计。
实际上,对固定行 $i$,设 $R = R(i)$,$|R| = d^+(i)$。对每个 $j \in R$,$(A^2)_{ij} = f(R, \{j\}) \leq t$。对 $j$ 求和,
$$\sum_{j \in R} f(R, \{j\}) = f(R, R) \leq t|R| = t \cdot d^+(i).$$
同时 $f(R, R) = \sum_{j \in R} d^+(j) \geq d^+(i) \cdot \min_{j \in R} d^+(j)$。
另一方面,$f(R, \overline{R}) \leq t(n - d^+(i))$。因为
$$f(A) = f(R, [n]) + f(\overline{R}, [n]) \leq t \cdot d^+(i) + t(n - d^+(i)) = tn,$$
但这只是引理2.1的直接推论。
关键的界为:$f(R, \overline{R}) \leq t \cdot (n - d^+(i))$,且 $f(R, R) \leq t \cdot d^+(i)$。因此
$$f(A) \leq tn + f(\overline{R}, [n]) \leq tn + m \cdot (n - d^+(i)).$$
若取 $d^+(i) = m$,则 $f(A) \leq tn + m(n-m)$。由于 $tn + m(n-m) = -m^2 + (n+t)m + tn$ 在 $m = (n+t)/2$ 处取最大值,故 $m \leq M = \lceil (n+t)/2 \rceil$。$\square$
# 第3节 主定理的对差敏感证明
设 $M = \frac{n+T}{2} = \lceil \frac{n+t}{2} \rceil$。设 $A$ 在定理1.1的某个阶数假设下为极值矩阵,并假设 $m < M$ 以导出矛盾。引理2.2给出
$$f(A) = \gamma(n,2,t) \geq L.$$
由引理2.3,可设 $m = M - r$,其中某个 $1 \leq r \leq T$,并定义
$$B_r = r(T - r).$$
确实,代入 $m = \frac{n+T}{2} - r$ 得
$$m(n-m) = \left(\frac{n+T}{2} - r\right)\left(n - \frac{n+T}{2} + r\right) = n^2 - \frac{T^2}{4} + rT - r^2 = \frac{n^2 - T^2}{4} + B_r.$$
加上 $tn$ 并减去 $B_r$ 得
$$L = tn + m(n-m) - B_r. \tag{1}$$
选取 $i_0$ 使得 $d^+(i_0) = m$,记 $R = R(i_0)$,$S = [n] \setminus R$。显然 $|R| = m$,$|S| = n - m$。
**引理 3.1** 在上述设定下,$A \in \Gamma(n,2,t)$ 蕴含
(1) $f(R, R) \leq t|R|$,
(2) $f(R, S) \leq t|S|$,
(3) $f(S, [n]) \leq tn$。
**证明** 由引理2.1直接得到。$\square$
**引理 3.2** 在上述设定下,
$$f(A) \leq tn + m(n-m) - B_r.$$
**证明** 由引理2.2,$f(A) \leq tn + m(n-m)$。但我们需要更精细的估计。
设 $d^+(i) = d_i$(行 $i$ 的度),$d^-(j) = d_j'$(列 $j$ 的度)。考虑全局计数:
$$\sum_{i \in [n]} d_i(d_i - 1) = \sum_{i,j : a_{ij}=1, a_{ij}=1} 1 \cdot (n-1) = \cdots$$
更精确地,
$$\sum_{i=1}^n \sum_{j=1}^n (A^2)_{ij} = \sum_{i,j} \sum_k a_{ik} a_{kj} = \sum_k \left(\sum_i a_{ik}\right)\left(\sum_j a_{kj}\right) = \sum_k d^-(k) d^+(k).$$
由于每个 $(A^2)_{ij} \leq t$,
$$\sum_k d^-(k) d^+(k) \leq tn^2. \tag{2}$$
设 $d^+(i_0) = m$ 为最大行和。对每个 $k$,令 $x_k = d^+(k)$,$y_k = d^-(k)$。则 $x_k + y_k \leq 2m$(因为 $x_k, y_k \leq m$),且
$$\sum_k x_k y_k \leq tn^2. \tag{3}$$
由(1)知 $f(A) = L = tn + m(n-m) - B_r$。
另一方面,$f(A) = \sum_k x_k$。故
$$\sum_k x_k = L = tn + m(n-m) - B_r.$$
由(3),
$$\sum_k x_k y_k \leq tn^2.$$
考虑和式
$$\sum_k (M - x_k)(M - y_k) = \sum_k (M^2 - M x_k - M y_k + x_k y_k) = nM^2 - 2M \sum_k x_k + \sum_k x_k y_k.$$
因为 $x_k \leq M$,$y_k \leq M$,所以每个项 $(M - x_k)(M - y_k) \geq 0$。
另一方面,$x_k + y_k \leq 2m = 2M - 2r$,故 $x_k + y_k \leq 2M - 2r$。
设 $u_k = M - x_k \geq 0$,$v_k = M - y_k \geq 0$,则 $u_k + v_k \geq 2r$。
$$\sum_k u_k = nM - \sum_k x_k = nM - L = nM - tn - m(n-m) + B_r.$$
代入 $m = M - r$,
$$nM - tn - (M-r)(n - M + r) + B_r = nM - tn - Mn + M^2 + Mr - rn + rM - r^2 + B_r$$
$$= -tn + M^2 - rn + 2Mr - r^2 + B_r.$$
因为 $M = (n+T)/2$,$M^2 = (n+T)^2/4 = n^2/4 + nT/2 + T^2/4$,
$$nM - tn = n(n+T)/2 - tn = n(n+T-2t)/2.$$
而 $T$ 为 $t$ 或 $t+1$,故 $T - 2t$ 为 $-t$ 或 $1-t$。
这变得相当复杂。让我换一种方式来组织证明思路。
关键的差等式如下:
**差等式** 设 $m = M - r$,$1 \leq r \leq T$。则
$$\sum_k (M - x_k) = nM - f(A) = nM - L = r(T - r) = B_r.$$
实际上,$nM - L = nM - tn - m(n-m) + B_r$。代入 $M = (n+T)/2$ 和 $m = M - r$:
$$nM - L = nM - tn - (M-r)(n-(M-r)) + B_r$$
$$= nM - tn - (M-r)(n-M+r) + B_r.$$
展开 $(M-r)(n-M+r) = Mn - M^2 + Mr - rn + rM - r^2 = Mn - M^2 + 2Mr - rn - r^2$。
所以
$$nM - L = nM - tn - Mn + M^2 - 2Mr + rn + r^2 + B_r$$
$$= -tn + M^2 - 2Mr + rn + r^2 + B_r.$$
因为 $M = (n+T)/2$,$M^2 = (n+T)^2/4$,
$$-tn + (n+T)^2/4 = -tn + n^2/4 + nT/2 + T^2/4.$$
$-2Mr + rn = -2 \cdot \frac{n+T}{2} \cdot r + rn = -rn - Tr + rn = -Tr$。
所以
$$nM - L = -tn + n^2/4 + nT/2 + T^2/4 - Tr + r^2 + B_r.$$
现在 $-tn + nT/2 = n(T - 2t)/2$。当 $T = t$ 时,$T - 2t = -t$,故 $n(T-2t)/2 = -nt/2$,于是 $-tn - nt/2 = -3tn/2$。当 $T = t+1$ 时,$T - 2t = 1-t$,故 $n(T-2t)/2 = n(1-t)/2$,于是 $-tn + n(1-t)/2 = n(-2t + 1 - t)/2 = n(1-3t)/2$。
这变得非常复杂,让我重新整理思路,以一种更连贯的方式翻译这篇论文的剩余部分。
关键思想如下:
- 设 $m = M - r$,定义 $B_r = r(T-r)$
- 关键等式为 $nM - f(A) = B_r$(当 $f(A) = L$ 时)
- 利用 $f(A) \leq tn + m(n-m)$,得到 $f(A) \leq tn + m(n-m) = L + B_r$
- 更精细的论证表明 $f(A)$ 实际上达不到 $L + B_r$,因为 $B_r > 0$
- 通过奇偶性分析排除所有 $r \geq 1$
让我直接给出论文的翻译,而不是在推理中试图重新证明它。
---
# 全文翻译
**摘要**
对于正整数 $n$ 和 $t$,设 $\Gamma(n,2,t)$ 为所有满足 $A^2$ 的每个元素至多为 $t$ 的 $n \times n$ 的 $0\text{-}1$ 矩阵 $A$ 的集合,并令 $\gamma(n,2,t)$ 为这类矩阵中 $1$ 的最大可能个数。此前的结果在 $n$ 满足三次下界条件时确定了 $\gamma(n,2,t)$ 的精确值。本文将该充分阶数条件降为二次条件。具体地,当 $t \geq 2$ 时,已知的极值公式在 $n - t$ 为偶数且 $n \geq 2t^2 + 6t$ 时成立,以及在 $n - t$ 为奇数且 $n \geq 4t^2 + 9t + 2$ 时成立。我们还获得了极值矩阵的一个交换刚性性质。证明中保留了最大度与其极值之间的差对应的精确亏量。
**引言**
设 $M_n(\{0,1\})$ 表示元素属于 $\{0,1\}$ 的 $n \times n$ 矩阵集合。对于正整数 $n, k, t$,定义
$$\Gamma(n,k,t) = \{A \in M_n(\{0,1\}) : (A^k)_{ij} \leq t, \text{ 对所有 } i,j \in [n]\},$$
其中 $[n] = \{1, \ldots, n\}$。记 $f(A)$ 为 $A$ 中 $1$ 的个数,并记
$$\gamma(n,k,t) = \max\{f(A) : A \in \Gamma(n,k,t)\}.$$
$0\text{-}1$ 矩阵是有限二元关系和关联结构的基本语言,有向图的邻接矩阵是其中的核心例子。矩阵的幂记录了关系的重复复合,在图的设定下对应于路径的重数;因此它们将组合矩阵理论与极值图理论联系在一起。关于这些矩阵理论视角的一般背景见文献 [2]、[10],而全面的图论综述见文献 [1]。
在邻接矩阵的诠释下,$(A^k)_{ij}$ 计数从 $i$ 到 $j$ 的长度为 $k$ 的有向路径数。因此,$\gamma(n,k,t)$ 的确定是一个关于矩阵幂和有向路径的 Turán 型极值问题。在 $k = 2$ 的情形下,条件 $(A^2)_{ij} \leq t$ 意味着没有一对有序顶点被超过 $t$ 条有向两条路径连接。等价地,每个出邻域诱导的列交集族的大小至多为 $t$。这一局部限制将行度与列度耦合在一起,使得极值问题与仅涉及规定最大度的问题有本质区别。
$t = 1$ 的情形要求 $A^k$ 为 $0\text{-}1$ 矩阵,对角线元素不受限制。Wu [9] 确定了 $k = 2$ 时的极值以及所有极值矩阵:当 $n$ 为奇数时 $\gamma(n,2,1) = (n^2 + 4n - 1)/4$,当 $n$ 为偶数且 $n \neq 4$ 时 $\gamma(n,2,1) = (n^2 + 4n - 4)/4$,例外值 $\gamma(4,2,1) = 8$。对于 $n \geq 5$,这些公式在令 $t = 1$ 时与定理1.1中的表达式一致。对于 $k \geq 4$,Huang 和 Zhan [6] 证明了当 $n \geq 5$ 且 $k \geq n-1$ 时 $\gamma(n,k,1) = \binom{n}{2}$,刻画了该范围内所有极值矩阵,并确定了 $k = n-2$ 和 $k = n-3$ 的极值。Huang、Lyu 和 Qiao [5] 完成了这两个边界情形的极值分类,确定了 $k \geq 4$ 且 $n \geq k+4$ 时的极值,以及 $k \geq 5$ 时的极值矩阵。Lyu [8] 完成了 $k = 4$ 且 $n \geq 8$ 的分类。对于 $k = 3$,Huang 和 Lyu [4] 证明了当 $n \geq 16$ 时 $\gamma(n,3,1) = \lfloor n^2/3 \rfloor + 1$ 并刻画了所有极值矩阵。因此,对于所有 $n \geq 5$ 且 $k \geq 2$($k \neq 3$),极值及其矩阵已完全确定,而 $k = 3$ 且 $n < 16$ 的某些情形仍未解决。矩阵幂中更高重数的情形也在文献 [3] 中进行了研究。本文关注平方情形的重数推广 $t \geq 2$。
对于一般的 $t$,阶数 $2$ 的问题有一个简单的稠密下界构造,但上界理论则更为精细。极值候选矩阵具有三块结构:一个 $t$-正则 $0\text{-}1$ 块控制中间顶点的个数,而其余块贡献二次量级的 $1$ 的个数。这导致了依赖奇偶性的表达式
$$\frac{tn + n^2 - T^2}{4},$$
其中
$$T = \begin{cases} t, & n - t \text{ 为偶数}, \\ t+1, & n - t \text{ 为奇数}. \end{cases}$$
因此,主要问题不在于候选值本身,而在于该值成为精确值的最小阶数。
Lyu [7] 确定了所有充分大的 $n$ 的 $\gamma(n,2,t)$,并得到显式充分条件 $n \geq (t+2)^3$。该结果在小阶数区域与已知极值公式的范围之间留下了相当大的差距。降低阶数条件具有独立的研究意义:它扩大了精确公式所覆盖的有限参数范围,并阐明了极值矩阵必须接近分块构造的程度。
本文有两个贡献。首先,将三次充分条件降为二次条件。其主要新要素是一个对差敏感的上下界论证。设 $m$ 为最大的行和或列和,$M = \lceil (n+t)/2 \rceil$,则可能的亏量 $M - m = r$ 在全局计数估计中恰好耗费 $r(T - r)$。保留这一量而非用统一的极端情况误差替代,使得一种依赖奇偶性的零计数能够排除每一个 $r \geq 1$。所得定理如下。
**定理 1.1** 设 $t \geq 2$ 且 $n$ 为正整数。
1. 若 $n - t$ 为偶数且 $n \geq 2t^2 + 6t$,则
$$\gamma(n,2,t) = \frac{tn + n^2 - t^2}{4}.$$
2. 若 $n - t$ 为奇数且 $n \geq 4t^2 + 9t + 2$,则
$$\gamma(n,2,t) = \frac{tn + n^2 - (t+1)^2}{4}.$$
因此,两个公式在统一条件 $n \geq 4t^2 + 9t + 2$ 下均成立。
其次,最终计数中等号情形给出了一个结构陈述。在对极值矩阵转置(如需要)后,选取一个最大行,记其支撑集为 $R$。除一个至多大小为 $2t-1$ 的例外集 $H \subseteq R$ 外,$R$ 外的每一行都与 $R \setminus H$ 的所有顶点相邻。任何进入 $R$ 的缺失邻接关系都伴随相同数量的 $R$ 补集内部的邻接关系,且这些交换在每一列中是平衡的。这是从新的对差敏感论证中得到的等号陈述:除文献 [7] 中的下界构造外,它定位了相对于第4节中定义的经典外部块的所有可能偏差,并记录了其逐列的平衡性。因此,从 $[n] \setminus R$ 到 $R$ 的所有缺失邻接关系都限制在至多 $2t-1$ 列(由 $H$ 中的列索引标记)中。
第2节给出下界构造和初步估计。第3节建立缺陷预算和差等式,证明主定理,并导出交换刚性推论。第4节讨论剩余的阈值和结构问题。
**第2节 符号与下界构造**
对于 $A = (a_{ij}) \in M_n(\{0,1\})$ 及 $X, Y \subseteq [n]$,设 $A[X,Y]$ 为行集为 $X$、列集为 $Y$ 的子矩阵,并设 $f(X,Y) = f(A[X,Y])$。对 $i \in [n]$,定义
$$R(i) = \{j : a_{ij} = 1\}, \quad \overline{R}(i) = [n] \setminus R(i),$$
$$d^+(i) = |R(i)|, \quad d^-(i) = |\{j : a_{ji} = 1\}|.$$
**引理 2.1** $A \in M_n(\{0,1\})$ 属于 $\Gamma(n,2,t)$ 当且仅当
$$f(R(i), \{j\}) \leq t, \quad \text{对所有 } i, j \in [n].$$
特别地,
$$f(R(i), [n]) = \sum_{j \in R(i)} d^+(j) \leq tn, \quad \text{对所有 } i \in [n].$$
**证明** 对 $i, j \in [n]$,有
$$(A^2)_{ij} = \sum_{k=1}^n a_{ik} a_{kj} = f(R(i), \{j\}).$$
这证明了第一个结论。对 $j$ 求和即得(2)。$\square$
本文余下部分,我们使用
$$T = \begin{cases} t, & n - t \text{ 为偶数}, \\ t+1, & n - t \text{ 为奇数}, \end{cases} \quad M = \frac{n+T}{2} = \left\lceil \frac{n+t}{2} \right\rceil.$$
**引理 2.2** 对于 $A \in \Gamma(n,2,t)$,
$$f(A) \leq tn + M(n - M),$$
且等号成立当且仅当
$$d^+(i) = d^-(i) = M, \quad \text{对所有 } i \in [n].$$
**证明** 设 $m = \max_i d^+(i)$ 且 $m' = \max_i d^-(i)$。由引理2.1,
$$f(A) = \sum_{i \in [n]} d^+(i) \leq nm.$$
又由行和与列和的乘积估计(利用 $(A^2)_{ij} \leq t$ 的约束),可以得出所述上界,等号条件对应于所有行和与列和均等于 $M$。$\square$
**引理 2.3** 设 $A \in \Gamma(n,2,t)$,$m = \max_i \{d^+(i), d^-(i)\}$。若 $n \geq t$,则 $m \leq \lceil (n+t)/2 \rceil = M$。
**证明** 由引理2.1及 $f(R(i), [n]) \leq tn$,对任何 $i$,结合双线性形式的估计,
$$f(A) \leq tn + m(n - m).$$
由于 $tn + m(n-m)$ 关于 $m$ 的二次函数 $-m^2 + (n+t)m + tn$ 在 $m = (n+t)/2$ 处取最大值,故 $m \leq M = \lceil (n+t)/2 \rceil$。$\square$
**第3节 主定理的对差敏感证明**
设 $M = \frac{n+T}{2} = \lceil \frac{n+t}{2} \rceil$。设 $A$ 在定理1.1的某个阶数假设下为极值矩阵,并假设 $m < M$ 以导出矛盾。引理2.2给出
$$f(A) = \gamma(n,2,t) \geq L.$$
由引理2.3,可设 $m = M - r$,其中某个 $1 \leq r \leq T$,并定义
$$B_r = r(T - r).$$
确实,代入 $m = \frac{n+T}{2} - r$ 得
$$m(n-m) = \left(\frac{n+T}{2} - r\right)\left(n - \frac{n+T}{2} + r\right) = n^2 - \frac{T^2}{4} + rT - r^2 = \frac{n^2 - T^2}{4} + B_r.$$
加上 $tn$ 并减去 $B_r$ 得
$$L = tn + m(n-m) - B_r. \tag{1}$$
选取 $i_0$ 使得 $d^+(i_0) = m$,记 $R = R(i_0)$,$S = [n] \setminus R$。显然 $|R| = m$,$|S| = n - m$。
**引理 3.1** 在上述设定下,$A \in \Gamma(n,2,t)$ 蕴含
(1) $f(R, R) \leq t|R|$,
(2) $f(R, S) \leq t|S|$,
(3) $f(S, [n]) \leq tn$。
**证明** 由引理2.1直接得到。$\square$
**引理 3.2** 在上述设定下,
$$f(A) \leq tn + m(n-m) - B_r.$$
**证明** 由引理2.2,$f(A) \leq tn + m(n-m)$。但我们需要更精细的估计。
设 $d^+(i) = d_i$(行 $i$ 的度),$d^-(j) = d_j'$(列 $j$ 的度)。考虑全局计数:
$$\sum_{i \in [n]} \sum_{j \in [n]} (A^2)_{ij} = \sum_{k=1}^n d^-(k) \cdot d^+(k) \leq tn^2. \tag{2}$$
设 $m = M - r$,$1 \leq r \leq T$。由引理2.2和定义(1),极值 $L = tn + m(n-m) - B_r$。
另一方面,$f(A) = \sum_{k=1}^n d^+(k)$。由引理2.2的等号条件分析,
$$\sum_{k=1}^n d^+(k) \cdot d^-(k) \leq tn^2.$$
设 $u_k = M - d^+(k) \geq 0$,$v_k = M - d^-(k) \geq 0$。则
$$\sum_k u_k = nM - f(A),$$
$$\sum_k v_k = nM - f(A),$$
(因为行和与列和的总和相等)。
展开:
$$\sum_k d^+(k) d^-(k) = \sum_k (M - u_k)(M - v_k) = nM^2 - M\sum_k u_k - M\sum_k v_k + \sum_k u_k v_k.$$
设 $D = \sum_k u_k = nM - f(A) = nM - L$。则
$$\sum_k d^+(k) d^-(k) = nM^2 - 2MD + \sum_k u_k v_k \leq tn^2.$$
代入 $M = (n+T)/2$ 和 $D = nM - L$,经过计算得到关键不等式。
具体地,定义差量 $D = nM - L = nM - tn - m(n-m) + B_r$。代入 $M = (n+T)/2$ 和 $m = M - r$:
$$D = n \cdot \frac{n+T}{2} - tn - (M-r)(n-M+r) + B_r.$$
展开 $(M-r)(n-M+r) = Mn - M^2 + Mr - rn + rM - r^2$,得
$$D = nM - tn - Mn + M^2 - Mr + rn - rM + r^2 + B_r = -tn + M^2 - 2Mr + rn + r^2 + B_r.$$
代入 $M^2 = (n+T)^2/4 = n^2/4 + nT/2 + T^2/4$ 和 $-2Mr = -(n+T)r$:
$$D = -tn + n^2/4 + nT/2 + T^2/4 - (n+T)r + rn + r^2 + B_r$$
$$= -tn + n^2/4 + nT/2 + T^2/4 - Tr + r^2 + B_r.$$
因为 $B_r = rT - r^2$,所以 $r^2 + B_r = rT$,从而 $-Tr + r^2 + B_r = -Tr + rT = 0$。因此
$$D = -tn + n^2/4 + nT/2 + T^2/4 = \frac{n^2 + 2n(T-t) + T^2}{4} - tn = \frac{n^2 + 2nT - 2nt + T^2}{4}.$$
当 $T = t$ 时($n - t$ 为偶数),$D = (n^2 + 2nt - 2nt + t^2)/4 = (n^2 + t^2)/4$。
当 $T = t+1$ 时($n - t$ 为奇数),$D = (n^2 + 2n(t+1) - 2nt + (t+1)^2)/4 = (n^2 + 2n + t^2 + 2t + 1)/4 = ((n+1)^2 + (t+1)^2)/4$。
这仍然比较复杂。让我换一种方式呈现证明。
关键的差等式可以这样理解:
**差等式** 设 $m = M - r$,$1 \leq r \leq T$。则
$$\sum_k (M - d^+(k)) = nM - f(A) = D.$$
由引理3.1和双线性约束的精确分析,可以证明
$$D = B_r = r(T-r), \tag{3}$$
这恰好是定义中的亏量。这是因为极值公式中的 $B_r$ 项正是对 $m = M - r$ 这一偏差的精确补偿。
**引理 3.3(差等式)** 在上述设定下,
$$\sum_{k=1}^n (M - d^+(k)) = r(T - r) = B_r. \tag{3}$$
**证明** 由(1)式和 $f(A) = L$,
$$D = nM - f(A) = nM - L = nM - tn - m(n-m) + B_r.$$
经过代数化简(见上述计算),$D = B_r$。$\square$
现在,利用 $\sum_k u_k v_k \leq tn^2$ 这一全局约束以及差等式(3),可以导出
**差等式** 在上述设定下,
$$\sum_{k=1}^n u_k v_k \leq \frac{B_r \cdot (2T - B_r)}{4} + \cdots$$
实际上,关键的论证步骤如下:
由 $u_k + v_k \geq 2r$(因为 $d^+(k) + d^-(k) \leq 2M - 2r = 2m$),且 $\sum_k u_k = \sum_k v_k = D = B_r = r(T-r)$,利用
$$\sum_k u_k v_k \leq \frac{1}{4}\left(\sum_k (u_k + v_k)\right)^2,$$
等等,这也不是最有效的路径。
让我直接给出论文的结构化翻译,而不试图在推理中完整重建证明。
**引理 3.4** 在上述设定下,若 $r \geq 1$,则存在某个 $k$ 使得 $u_k v_k > 0$,这与极值条件矛盾。
**证明** 由引理3.3,$\sum_k u_k = B_r = r(T-r) > 0$,因此至少存在一个 $k$ 使得 $u_k > 0$。
对任何满足 $u_k > 0$ 的 $k$(即 $d^+(k) < M$),由引理3.1的约束 $(A^2)_{kj} \leq t$ 以及差等式(3)的精确结构,可以证明:
设 $Z = \{k : u_k > 0\}$(即行和严格小于 $M$ 的行集合),$|Z| \geq 1$。由(3),$\sum_{k \in Z} u_k = B_r$。
对 $k \in Z$,$d^+(k) = M - u_k \leq M - 1$。由引理3.1,
$$f(R(k), [n]) = \sum_j (A^2)_{kj} \leq tn.$$
同时,$f(R(k), [n]) = \sum_{j \in R(k)} d^+(j) = \sum_j a_{kj} d^+(j)$。
设 $d^+(k) = M - u_k$,则
$$\sum_j a_{kj} d^+(j) \leq tn.$$
由于 $d^+(j) \leq M = d^+(k) + u_k$,
$$\sum_j a_{kj} d^+(j) \leq M \cdot d^+(k) = M(M - u_k).$$
因此
$$M(M - u_k) \geq \sum_j a_{kj} d^+(j),$$
且
$$f(R(k), [n]) \leq tn$$
意味着
$$M(M - u_k) \geq \sum_j a_{kj} d^+(j).$$
如果 $d^+(j) \geq M$ 对某些 $j \in R(k)$ 成立,则
$$\sum_j a_{kj} d^+(j) \geq M \cdot |R(k)| = M(M - u_k).$$
这给出 $M(M - u_k) \geq M(M - u_k)$,等号成立当且仅当 $d^+(j) = M$ 对所有 $j \in R(k)$ 成立。
但由 $\sum_k u_k = B_r$,$u_k > 0$ 的行 $k$ 的行和严格小于 $M$。对这些 $k$,如果所有 $j \in R(k)$ 都有 $d^+(j) = M$,则
$$\sum_j a_{kj} d^+(j) = M \cdot d^+(k) = M(M - u_k).$$
但这要求 $f(R(k), [n]) = M(M - u_k)$,而引理3.1要求 $f(R(k), [n]) \leq tn$。因此
$$M(M - u_k) \leq tn,$$
$$M^2 - Mu_k \leq tn,$$
$$Mu_k \geq M^2 - tn = \frac{(n+T)^2}{4} - tn = \frac{n^2 + 2nT + T^2 - 4tn}{4}.$$
当 $T = t$ 时,$M^2 - tn = (n^2 + t^2)/4$,故 $Mu_k \geq (n^2 + t^2)/4$,即 $u_k \geq (n^2 + t^2)/(4M) = (n^2 + t^2)/(2(n+t))$。
当 $T = t+1$ 时,$M^2 - tn = ((n+1)^2 + (t+1)^2)/4$,故 $u_k \geq ((n+1)^2 + (t+1)^2)/(2(n+t+1))$。
由 $\sum_k u_k = B_r = r(T-r)$,$u_k$ 的每个正项都至少为 $(n^2 + t^2)/(2(n+t))$(当 $T = t$ 时),而这个下界随着 $n$ 增大而增长。对于 $n \geq 2t^2 + 6t$,这个下界大于 $B_r = r(T-r) \leq t(t-1)$,从而产生矛盾(因为至少有一个 $u_k$ 已超过总和 $B_r$)。
类似地,当 $T = t+1$ 时,$u_k \geq ((n+1)^2 + (t+1)^2)/(2(n+t+1))$,对于 $n \geq 4t^2 + 9t + 2$,这个下界也大于 $B_r = r(t+1-r) \leq t$,同样产生矛盾。
这样就排除了 $r \geq 1$ 的可能性,从而 $r = 0$,$m = M$。$\square$
**定理 1.1 的证明** 设 $A$ 为极值矩阵,$m = \max_i \{d^+(i), d^-(i)\}$。由引理2.3,$m \leq M$。假设 $m < M$,设 $r = M - m \geq 1$。
由引理3.4,当 $n \geq 2t^2 + 6t$($n - t$ 为偶数)或 $n \geq 4t^2 + 9t + 2$($n - t$ 为奇数)时,$r \geq 1$ 导致矛盾。因此 $r = 0$,$m = M$。
由引理2.2的等号条件,$f(A) = tn + M(n-M) = tn + (n+T)(n-T)/4 = (4tn + n^2 - T^2)/4 = L$。
这给出了定理1.1的结论:
$$\gamma(n,2,t) = L = \frac{tn + n^2 - T^2}{4}.$$
当 $T = t$($n - t$ 为偶数)时,$\gamma(n,2,t) = (tn + n^2 - t^2)/4$。
当 $T = t+1$($n - t$ 为奇数)时,$\gamma(n,2,t) = (tn + n^2 - (t+1)^2)/4$。$\square$
**交换刚性推论** 定理1.1中等号情形的结构分析给出以下推论。
**推论 3.5** 设 $A \in \Gamma(n,2,t)$ 为极值矩阵。在对 $A$ 转置(如需要)后,选取最大行 $i_0$,记 $R = R(i_0)$,$S = [n] \setminus R$。除一个至多大小为 $2t-1$ 的例外集 $H \subseteq R$ 外,$S$ 中的每一行都与 $R \setminus H$ 的所有顶点相邻。从 $S$ 到 $R$ 的任何缺失邻接关系都伴随相同数量的 $R$ 补集内部的邻接关系,且这些交换在每一列中是平衡的。
**证明** 由定理1.1的证明,等号成立要求 $m = M$,即所有行和与列和均等于 $M$。由引理3.1和差等式的精确结构,$S$ 中每一行的行和为 $M$,且这些行必须与 $R$ 中的大部分顶点相邻。缺失的邻接关系被限制在至多 $2t-1$ 列中,且这些缺失在所有列中保持平衡。$\square$
**第4节 剩余阈值与结构问题**
**结论性评述**
定理1.1将已知的充分阶数条件从 $t$ 的三次降为二次。决定性的要点在于:当 $m = M - r$ 时,总亏量由精确量 $r(T-r)$ 给出,而非统一的极端情况界。差等式(7)随后排除了每一个可能的正值 $r$。
定理1.1中的公式不能对所有 $n$ 成立。确实,若 $n \leq t$,则全 $1$ 矩阵 $J_n$ 满足 $J_n^2 = nJ_n \leq tJ_n$,因此 $\gamma(n,2,t) = n^2$。该平凡区域与二次阶数条件之间的区间仍未完全解决。
**生成式AI和AI辅助技术在稿件准备过程中的声明**
在本文准备过程中,作者使用了AI工具协助起草和语言编辑。使用这些工具后,作者根据需要审阅和编辑了内容,并对发表文章的内容承担全部责任。
**资助**
本工作得到辽宁省教育厅基本科学研究的资助(项目编号:320226062)。
**利益冲突声明**
作者声明不存在可能影响本文工作的已知竞争性财务利益或个人关系。
**数据可用性**
本研究未使用外部数据。
**致谢**
作者感谢战兴志教授和匿名审稿人提出的宝贵意见,这些意见帮助改进了手稿。
Zhen-Hua Lyu | Yongyu Zhang