关于Hoffman界的推广

A Generalization of Hoffman’s Bound

摘要: Hoffman界是用邻接矩阵的特征值来表示正则图的独立数的上界。本文中，我们通过对独立数的概念进行推广，从而得到了一个Hoffman界的推广。作为一个应用，我们得到了EKR定理的饱和性，即当$n\ge 2k+1$ 时，对于集族$ℱ\in \left(\begin{array}{c}\left[n\right]\\ k\end{array}\right)$ ，如果$\left|ℱ\right|>\left(1+\delta \right)\left(\begin{array}{c}n-1\\ k-1\end{array}\right)$ ，那么$ℱ$ 中的2-匹配数至少为$\delta \left(1+\delta \right)\left(\begin{array}{c}n-1\\ k-1\end{array}\right)\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)$ 。同时，我们证明了当$n\ge 2k+1$ 时，对于集族$\mathcal{A},ℬ\in \left(\begin{array}{c}\left[n\right]\\ k\end{array}\right)$ ，如果$\left|\mathcal{A}\right|\left|ℬ\right|>\left(1+\delta \right){\left(\begin{array}{c}n-1\\ k-1\end{array}\right)}^2$ ，那么$\mathcal{A},ℬ$ 中的2-匹配数至少为$\frac{n\delta }{2\left(n-k\right)}\left(\begin{array}{c}n-1\\ k-1\end{array}\right)\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)$ 。

Abstract: Hoffman’s bound is an upper on the independence number of a regular graph in terms of the eigenvalues of the adjacency matrix. In this paper, we get a generalization of Hoffman’s bound by extending of the definition of the independence number. As an application, we get the saturation of EKR theorem. In other words, we show that if $ℱ\in \left(\begin{array}{c}\left[n\right]\\ k\end{array}\right)\left(n\ge 2k+1\right)$ with $\left|ℱ\right|>\left(1+\delta \right)\left(\begin{array}{c}n-1\\ k-1\end{array}\right)$ , then the number of 2-matching in $ℱ$ is greater than $\delta \left(1+\delta \right)\left(\begin{array}{c}n-1\\ k-1\end{array}\right)\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)$ . Meanwhile, we show that if $\mathcal{A},ℬ\in \left(\begin{array}{c}\left[n\right]\\ k\end{array}\right)\left(n\ge 2k+1\right)$ with $\left|\mathcal{A}\right|\left|ℬ\right|>\left(1+\delta \right){\left(\begin{array}{c}n-1\\ k-1\end{array}\right)}^2$ , then the number of 2-matching in $\mathcal{A},ℬ$ is greater than $\frac{n\delta }{2\left(n-k\right)}\left(\begin{array}{c}n-1\\ k-1\end{array}\right)\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)$ .

1. 引言

记$\left[n\right]=\left\{1,2,\cdots ,n\right\}$ ，用$\left(\begin{array}{c}\left[n\right]\\ k\end{array}\right)$ 表示$\left[n\right]$ 中所有k元子集组成的集族，我们称$\left(\begin{array}{c}\left[n\right]\\ k\end{array}\right)$ 的一个子集族为一个k一致集族或一个k一致超图。设$ℱ\subseteq \left(\begin{array}{c}\left[n\right]\\ k\end{array}\right)$ 是一个k一致集族，如果对任意的$F_1,F_2\in ℱ$ ，满足$F_1\cap F_2\ne \varnothing$ ，则称$ℱ$ 是一个相交集族。经典的Erdős-Ko-Rado (EKR)定理[1]表明，当$n\ge 2k$ 时，如果$ℱ\in \left(\begin{array}{c}\left[n\right]\\ k\end{array}\right)$ 是相交集族，那么$\left|ℱ\right|\le \left(\begin{array}{c}n-1\\ k-1\end{array}\right)$ 。特别地，当$n\ge 2k+1$ 时，满足等号成立的集族是唯一的，对应的集族为$ℱ$ 中所有的包含一个固定的元素的集合。类似地，设$\mathcal{A},ℬ$ 是集族，如果对任意的$A\in \mathcal{A}$ ，$B\in ℬ$ ，满足$A\cap B\ne \varnothing$ ，则称$\mathcal{A},ℬ$ 是交叉相交集族。Pyber [2]对EKR定理进行了推广，证明了当$n\ge 2k$ 时，如果$\mathcal{A},ℬ\in \left(\begin{array}{c}\left[n\right]\\ k\end{array}\right)$ 是交叉相交集族，那么$\left|\mathcal{A}\right|\left|ℬ\right|\le {\left(\begin{array}{c}n-1\\ k-1\end{array}\right)}^2$ 。特别地，当$\mathcal{A}=ℬ$ 时可以推出EKR定理。EKR定理被认为是极值组合的基础，其推广和应用已经研究了数年，文献[3]给出了EKR定理不同的证明，文献[4]给出了度版本的EKR定理，其它相关文献可查阅[5]。

设G是一个简单图，顶点集记为$V\left(G\right)=\left\{u_1,u_2,\cdots ,u_n\right\}$ ，边集记为$E\left(G\right)$ 。我们用$e\left(G\right)$ 表示图G中边的数量。如果图G每个顶点的度都相等且为d，我们就称图G是d-正则图。设$S\subseteq V\left(G\right)$ ，记$G\left[S\right]$ 为S在G中的导出子图，其顶点集为S，边集为G的边集中两个顶点均属于S的边组成的集合。独立集是指图中两两互不相邻的顶点构成的集合，用独立数$\alpha \left(G\right)$ 表示图G的最大独立集的大小，即$\alpha \left(G\right)=\max \left\{\left|S\right|:e\left(G\left[S\right]\right)=0\right\}$ 。邻接矩阵是表示图中顶点间相邻关系的矩阵，图G的邻接矩阵$A={\left(a_{ij}\right)}_{n\times n}$ 定义如下：

$a_{ij}=\{\begin{array}{c}1,u_i{u}_j\in E\left(G\right)\\ 0,u_i{u}_j\notin E\left(G\right)\end{array}$ .

显然A是对称矩阵。Hoffman界是用邻接矩阵的特征值来表示正则图的独立数的上界。然而Hoffman并没有发表他的结果，直到2021年Haemers [6]将其整理成文。

定理1.1 (Hoffman)对于n个顶点的d-正则图G，有$\alpha \left(G\right)\le -\frac{n{\lambda }_n}{d-{\lambda }_n}$ 。

证明：记图G的邻接矩阵为A。设矩阵A的n个特征值为${\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_n$ ，不妨设${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$ ，对应的特征向量分别记为$v_1,v_2,\cdots ,v_n$ 。由于图G是正则图，所以我们可以得到$A1=d1$ (其中$1$ 为全1列向量)，即$A{\left(1,1,\cdots ,1\right)}^{\text{T}}=d{\left(1,1,\cdots ,1\right)}^{\text{T}}$ ，也就是说${\lambda }_1=d$ 。于是${\lambda }_1$ 对应的特征向量为$v_1=\frac{1}{\sqrt{n}}{\left(1,1,\cdots ,1\right)}^{\text{T}}$ 。记S是图G的一个独立集，那么有$1_S^{\text{T}}A{1}_S=0$ ，其中$1_S$ 为S的特征向量，不妨记$1_S={\displaystyle \sum _{i=1}^n{\alpha }_i{v}_i}$ 。于是有

${\alpha }_1=\langle 1_S,v_1\rangle =\frac{\left|S\right|}{\sqrt{n}}$ , $\left|S\right|={\Vert 1_S\Vert }_2^2={\displaystyle \sum _{i=1}^n{\alpha }_i^2}$ .

根据$1_S^{\text{T}}A{1}_S=0$ 可得

${\left({\displaystyle \sum _{i=1}^n{\alpha }_i{v}_i}\right)}^{\text{T}}A\left({\displaystyle \sum _{i=1}^n{\alpha }_i{v}_i}\right)=0$ ,

即${\displaystyle \sum _{i=1}^n{\lambda }_i{\alpha }_i^2}=0$ ，于是

${\lambda }_1{\alpha }_1^2+{\displaystyle \sum _{i=2}^n{\lambda }_i{\alpha }_i^2}=d{\alpha }_1^2+{\displaystyle \sum _{i=2}^n{\lambda }_i{\alpha }_i^2}=0$ ,

放缩可得

$d{\alpha }_1^2+{\lambda }_n{\displaystyle \sum _{i=2}^n{\alpha }_i^2}\le 0$ ，

其中${\alpha }_1^2=\frac{{\left|S\right|}^2}{n}$ ，${\displaystyle \sum _{i=2}^n{\alpha }_i^2}=\left|S\right|-{\alpha }_1^2=\left|S\right|-\frac{{\left|S\right|}^2}{n}$ ，代入上式可得

$d\frac{{\left|S\right|}^2}{n}+{\lambda }_n\left(\left|S\right|-\frac{{\left|S\right|}^2}{n}\right)\le 0$ ,

化简可得$\left|S\right|\le -\frac{n{\lambda }_n}{d-{\lambda }_n}$ ，于是图G的独立数$\alpha \left(G\right)\le -\frac{n{\lambda }_n}{d-{\lambda }_n}$ 。定理1.1即证。

当$n\ge 2k$ 时，Kneser图$KG\left(n,k\right)$ 的定义如下：顶点集为$\left[n\right]$ 的所有k元子集组成的集族，即$V\left(KG\left(n,k\right)\right)=\left(\begin{array}{c}\left[n\right]\\ k\end{array}\right)$ ，两个顶点之间连边当且仅当这两个顶点对应的k元子集是不相交的，即边集为$E\left(KG\left(n,k\right)\right)=\left\{\left(F_1,F_2\right):F_1,F_2\in \left(\begin{array}{c}\left[n\right]\\ k\end{array}\right),F_1\cap F_2=\varnothing \right\}$ 。特别地，$KG\left(5,2\right)$ 即为Peterson图。由定义可知，$KG\left(n,k\right)$ 是包含$\left(\begin{array}{c}n\\ k\end{array}\right)$ 个顶点的$\left(\begin{array}{c}n-k\\ k\end{array}\right)$ 正则图。Lováse [7]证明了Kneser图$KG\left(n,k\right)$ 的邻接矩阵的特征值为${\left(-1\right)}^j\left(\begin{array}{c}n-k-j\\ k-j\end{array}\right)$ ，其中$1\le j\le k$ ，因此最大特征值${\lambda }_1=\left(\begin{array}{c}n-k\\ k\end{array}\right)$ ，最小特征值${\lambda }_{\left(\begin{array}{c}n\\ k\end{array}\right)}=-\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)$ 。根据定理1.1，我们可以得到Kneser图的独立数$\alpha \left(KG\left(n,k\right)\right)\le \frac{\left(\begin{array}{c}n\\ k\end{array}\right)\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)}{\left(\begin{array}{c}n-k\\ k\end{array}\right)+\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)}=\frac{\left(\begin{array}{c}n\\ k\end{array}\right)}{\frac{n-k}{k}+1}=\left(\begin{array}{c}n-1\\ k-1\end{array}\right)$ ，这与EKR定理给出的结果是一致的。这是因为，Kneser图$KG\left(n,k\right)$ 中独立集的大小就等价于相交集族$\left(\begin{array}{c}\left[n\right]\\ k\end{array}\right)$ 的大小。

图的2-匹配是指图中顶点不交的边组成的集合，2-匹配数是指2-匹配中边的数量。在本文中，我们主要对独立数$\alpha \left(G\right)$ 的概念进行推广，从而得到Hoffman界的推广，并将其应用于Kneser图中，得到两个重要结论。

定理1.2当$n\ge 2k+1$ 时，对于集族$ℱ\in \left(\begin{array}{c}\left[n\right]\\ k\end{array}\right)$ ，如果$\left|ℱ\right|>\left(1+\delta \right)\left(\begin{array}{c}n-1\\ k-1\end{array}\right)$ ，那么$ℱ$ 中的2-匹配数至少为$\delta \left(1+\delta \right)\left(\begin{array}{c}n-1\\ k-1\end{array}\right)\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)$ 。

定理1.3当$n\ge 2k+1$ 时，对于集族$\mathcal{A},ℬ\in \left(\begin{array}{c}\left[n\right]\\ k\end{array}\right)$ ，如果$\left|\mathcal{A}\right|\left|ℬ\right|>\left(1+\delta \right){\left(\begin{array}{c}n-1\\ k-1\end{array}\right)}^2$ ，那么$\mathcal{A},ℬ$ 中的2-匹配数至少为$\frac{n\delta }{2\left(n-k\right)}\left(\begin{array}{c}n-1\\ k-1\end{array}\right)\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)$ 。

2. 定理1.2的证明

我们对独立数$\alpha \left(G\right)$ 进行推广。我们称$I\subseteq V\left(G\right)$ 为G的一个$\epsilon$ -近似独立集，如果满足$e\left(G\left[I\right]\right)\le \epsilon {\left|I\right|}^2$ 。用$\epsilon$ -近似独立数${\tilde{\alpha }}_{\epsilon }\left(G\right)$ 表示图G的最大$\epsilon$ -近似独立集的大小，即${\tilde{\alpha }}_{\epsilon }\left(G\right)=\max \left\{\left|I\right|:e\left(G\left[I\right]\right)\le \epsilon {\left|I\right|}^2\right\}$ 。显然，当$\epsilon =0$ 时$\epsilon$ -近似独立数${\tilde{\alpha }}_{\epsilon }\left(G\right)$ 即为独立数$\alpha \left(G\right)$ 。$\epsilon$ -近似独立集的引入，放松了独立集中边数为0的限制，使得我们可以研究图的更广泛的性质。因此，我们可以得到Hoffman界的如下推广。

定理2.1对于n的顶点的d-正则图G，有${\tilde{\alpha }}_{\epsilon }\left(G\right)\le -\frac{n{\lambda }_n}{d-{\lambda }_n-\epsilon n}$ 。

证明：记图G的邻接矩阵为A。设矩阵A的n个特征值为${\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_n$ ，不妨设${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$ ，对应的特征向量分别记为$v_1,v_2,\cdots ,v_n$ 。由于图G是正则图，所以我们可以得到$A1=d1$ (其中$1$ 为全1列向量)，即$A{\left(1,1,\cdots ,1\right)}^{\text{T}}=d{\left(1,1,\cdots ,1\right)}^{\text{T}}$ ，也就是说${\lambda }_1=d$ 。于是${\lambda }_1$ 对应的特征向量为$v_1=\frac{1}{\sqrt{n}}{\left(1,1,\cdots ,1\right)}^{\text{T}}$ 。记S是图G的一个$\epsilon$ -近似独立集，那么有$1_S^{\text{T}}A{1}_S\le \epsilon {\left|S\right|}^2$ ，其中$1_S$ 为S的特征向量，不妨记$1_S={\displaystyle \sum _{i=1}^n{\alpha }_i{v}_i}$ 。于是有

${\alpha }_1=\langle 1_S,v_1\rangle =\frac{\left|S\right|}{\sqrt{n}}$ , $\left|S\right|={\Vert 1_S\Vert }_2^2={\displaystyle \sum _{i=1}^n{\alpha }_i^2}$ .

根据$1_S^{\text{T}}A{1}_S\le \epsilon {\left|S\right|}^2$ 可得

${\left({\displaystyle \sum _{i=1}^n{\alpha }_i{v}_i}\right)}^{\text{T}}A\left({\displaystyle \sum _{i=1}^n{\alpha }_i{v}_i}\right)\le \epsilon {\left|S\right|}^2$ ,

即${\displaystyle \sum _{i=1}^n{\lambda }_i{\alpha }_i^2}\le \epsilon {\left|S\right|}^2$ ，于是

${\lambda }_1{\alpha }_1^2+{\displaystyle \sum _{i=2}^n{\lambda }_i{\alpha }_i^2}=d{\alpha }_1^2+{\displaystyle \sum _{i=2}^n{\lambda }_i{\alpha }_i^2}\le \epsilon {\left|S\right|}^2$ ,

放缩可得

$d{\alpha }_1^2+{\lambda }_n{\displaystyle \sum _{i=2}^n{\alpha }_i^2}\le \epsilon {\left|S\right|}^2$ ,

其中${\alpha }_1^2=\frac{{\left|S\right|}^2}{n}$ ，${\displaystyle \sum _{i=2}^n{\alpha }_i^2}=\left|S\right|-{\alpha }_1^2=\left|S\right|-\frac{{\left|S\right|}^2}{n}$ ，代入可得

$d\frac{{\left|S\right|}^2}{n}+{\lambda }_n\left(\left|S\right|-\frac{{\left|S\right|}^2}{n}\right)\le \epsilon {\left|S\right|}^2$ ,

化简可得$\left|S\right|\le -\frac{n{\lambda }_n}{d-{\lambda }_n-\epsilon n}$ ，于是图G的$\epsilon$ -近似独立数${\tilde{\alpha }}_{\epsilon }\left(G\right)\le -\frac{n{\lambda }_n}{d-{\lambda }_n-\epsilon n}$ 。定理2.1即证。

定理1.2的证明：令$\epsilon =\frac{\delta }{1+\delta }\cdot \frac{\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)}{\left(\begin{array}{c}n-1\\ k-1\end{array}\right)}$ 。下面我们将证明$ℱ$ 不是Kneser图中的$\epsilon$ -近似独立集。反证法假设$ℱ$ 是Kneser图中的一个$\epsilon$ -近似独立集，根据定理2.1，我们可以得到，$\left|ℱ\right|\le {\tilde{\alpha }}_{\epsilon }\left(KG\left(n,k\right)\right)$ ，即

$\left(1+\delta \right)\left(\begin{array}{c}n-1\\ k-1\end{array}\right)<\left|ℱ\right|\le \frac{\left(\begin{array}{c}n\\ k\end{array}\right)\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)}{\left(\begin{array}{c}n-k\\ k\end{array}\right)+\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)-\epsilon \left(\begin{array}{c}n\\ k\end{array}\right)}$ ,

不等式两边同时除以$\left(\begin{array}{c}n-1\\ k-1\end{array}\right)$ ，可得

$1+\delta <\frac{\frac{n}{k}\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)}{\left(\begin{array}{c}n-k\\ k\end{array}\right)+\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)-\epsilon \left(\begin{array}{c}n\\ k\end{array}\right)}$ ,

不等式右边分子分母同时除以$\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)$ ，可得

$1+\delta <\frac{\frac{n}{k}}{\frac{n-k}{k}+1-\epsilon \frac{\left(\begin{array}{c}n\\ k\end{array}\right)}{\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)}}$ .

不妨令$\epsilon =\frac{\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)}{\left(\begin{array}{c}n-1\\ k-1\end{array}\right)}\eta$ ，代入上式可得$1+\delta <\frac{\frac{n}{k}}{\frac{n}{k}-\frac{n}{k}\eta }$ ，化简可得$\eta >\frac{\delta }{1+\delta }$ ，于是

$\epsilon >\frac{\delta }{1+\delta }\cdot \frac{\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)}{\left(\begin{array}{c}n-1\\ k-1\end{array}\right)}$ ,

这与$\epsilon =\frac{\delta }{1+\delta }\cdot \frac{\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)}{\left(\begin{array}{c}n-1\\ k-1\end{array}\right)}$ 矛盾。于是$ℱ$ 不是Kneser图中的$\epsilon$ -近似独立集。

因此$ℱ$ 中的2-匹配数至少为

$\epsilon {\left|ℱ\right|}^2\ge \frac{\delta }{1+\delta }\cdot \frac{\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)}{\left(\begin{array}{c}n-1\\ k-1\end{array}\right)}\cdot {\left(1+\delta \right)}^2{\left(\begin{array}{c}n-1\\ k-1\end{array}\right)}^2=\delta \left(1+\delta \right)\left(\begin{array}{c}n-1\\ k-1\end{array}\right)\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)$ .

定理1.2通过对独立数$\alpha \left(G\right)$ 概念的推广，证明了EKR定理的饱和性。

3. 定理1.3的证明

设$I\subseteq V\left(G\right)$ ，$J\subseteq V\left(G\right)$ ，记$e\left(I,J\right)$ 为G的边集中一个顶点在I中、另一个顶点在J中的边组成的集合。我们对独立数$\alpha \left(G\right)$ 进行推广，定义$\beta \left(G\right)=\max \left\{\left|I\right|\left|J\right|:e\left(I,J\right)=0\right\}$ 。同时，我们对$\epsilon$ -近似独立数${\tilde{\alpha }}_{\epsilon }\left(G\right)$ 进行推广，定义${\tilde{\beta }}_{\epsilon }\left(G\right)=\max \left\{\left|I\right|\left|J\right|:e\left(I,J\right)\le \epsilon \left|I\right|\left|J\right|\right\}$ 。显然，当$\epsilon =0$ 时${\tilde{\beta }}_{\epsilon }\left(G\right)$ 即为$\beta \left(G\right)$ 。我们可以得到Hoffman界的如下推广。

定理3.1对于n的顶点的d-正则图G，有${\tilde{\beta }}_{\epsilon }\left(G\right)\le \frac{n^2{\lambda }_n^2}{d^2-{\lambda }_n^2+{\epsilon }^2{n}^2-2\epsilon dn}$ 。

证明：记图G的邻接矩阵为A。设矩阵A的n个特征值为${\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_n$ ，不妨设${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$ ，对应的特征向量分别记为$v_1,v_2,\cdots ,v_n$ 。因为图G是正则图，所以我们可以得到$A1=d1$ (其中$1$ 为全1列向量)，即$A{\left(1,1,\cdots ,1\right)}^{\text{T}}=d{\left(1,1,\cdots ,1\right)}^{\text{T}}$ ，也就是说${\lambda }_1=d$ 。于是${\lambda }_1$ 对应的特征向量为$v_1=\frac{1}{\sqrt{n}}{\left(1,1,\cdots ,1\right)}^{\text{T}}$ 。记$I\subseteq V\left(G\right)$ ，$J\subseteq V\left(G\right)$ 满足$e\left(I,J\right)\le \epsilon \left|I\right|\left|J\right|$ ，那么有$1_I^{\text{T}}A{1}_J\le \epsilon \left|I\right|\left|J\right|$ ，其中$1_I$ 为I的特征向量，$1_J$ 为J的特征向量，不妨记$1_I={\displaystyle \sum _{i=1}^n{\alpha }_i{v}_i}$ ，$1_J={\displaystyle \sum _{i=1}^n{\beta }_i{v}_i}$ 。于是有

${\alpha }_1=\langle 1_I,v_1\rangle =\frac{\left|I\right|}{\sqrt{n}}$ , ${\beta }_1=\langle 1_J,v_1\rangle =\frac{\left|J\right|}{\sqrt{n}}$ ,

$\left|I\right|={\Vert 1_I\Vert }_2^2={\displaystyle \sum _{i=1}^n{\alpha }_i^2}$ , $\left|J\right|={\Vert 1_J\Vert }_2^2={\displaystyle \sum _{i=1}^n{\beta }_i^2}$ .

根据$1_I^{\text{T}}A{1}_J\le \epsilon \left|I\right|\left|J\right|$ 可得

${\left({\displaystyle \sum _{i=1}^n{\alpha }_i{v}_i}\right)}^{\text{T}}A\left({\displaystyle \sum _{i=1}^n{\beta }_i{v}_i}\right)\le \epsilon \left|I\right|\left|J\right|$ ,

即${\displaystyle \sum _{i=1}^n{\lambda }_i{\alpha }_i}{\beta }_i\le \epsilon \left|I\right|\left|J\right|$ ，于是

${\lambda }_1{\alpha }_1{\beta }_1+{\displaystyle \sum _{i=2}^n{\lambda }_i{\alpha }_i{\beta }_i}=d{\alpha }_1{\beta }_1+{\displaystyle \sum _{i=2}^n{\lambda }_i{\alpha }_i{\beta }_i}\le \epsilon \left|I\right|\left|J\right|$ ,

放缩可得

$d{\alpha }_1{\beta }_1+{\lambda }_n{\displaystyle \sum _{i=2}^n{\alpha }_i{\beta }_i}\le \epsilon \left|I\right|\left|J\right|$ ,

根据Cauchy-Schwarz不等式可得${\displaystyle \sum _{i=2}^n{\alpha }_i{\beta }_i}\le \sqrt{\left({\displaystyle \sum _{i=2}^n{\alpha }_i^2}\right)\left({\displaystyle \sum _{i=2}^n{\beta }_i^2}\right)}$ ，将${\displaystyle \sum _{i=2}^n{\alpha }_i^2}=\left|I\right|-{\alpha }_1^2=\left|I\right|-\frac{{\left|I\right|}^2}{n}$ 和${\displaystyle \sum _{i=2}^n{\beta }_i^2}=\left|J\right|-{\beta }_1^2=\left|J\right|-\frac{{\left|J\right|}^2}{n}$ 代入可得${\displaystyle \sum _{i=2}^n{\alpha }_i{\beta }_i}\le \sqrt{\left(\left|I\right|-\frac{{\left|I\right|}^2}{n}\right)\left(\left|J\right|-\frac{{\left|J\right|}^2}{n}\right)}=\frac{1}{n}\sqrt{\left|I\right|\left|J\right|\left(n-\left|I\right|\right)\left(n-\left|J\right|\right)}$ ，又由于${\alpha }_1{\beta }_1=\frac{\left|I\right|\left|J\right|}{n}$ ，注意${\lambda }_n$ 为负数，于是可得

$d\frac{\left|I\right|\left|J\right|}{n}+\frac{{\lambda }_n}{n}\sqrt{\left|I\right|\left|J\right|\left(n-\left|I\right|\right)\left(n-\left|J\right|\right)}\le \epsilon \left|I\right|\left|J\right|$ ,

即

$\frac{{\lambda }_n}{n}\sqrt{\left|I\right|\left|J\right|\left(n-\left|I\right|\right)\left(n-\left|J\right|\right)}\le \left(\epsilon -\frac{d}{n}\right)\left|I\right|\left|J\right|$ ,

不等式两边同时平方，可得

${\left(\epsilon -\frac{d}{n}\right)}^2\left|I\right|\left|J\right|\le \frac{{\lambda }_n^2}{n^2}\left(n-\left|I\right|\right)\left(n-\left|J\right|\right)$ ,

化简可得$\left|I\right|\left|J\right|\le \frac{n^2{\lambda }_n^2}{d^2-{\lambda }_n^2+{\epsilon }^2{n}^2-2\epsilon dn}$ ，于是${\tilde{\beta }}_{\epsilon }\left(G\right)\le \frac{n^2{\lambda }_n^2}{d^2-{\lambda }_n^2+{\epsilon }^2{n}^2-2\epsilon dn}$ 。定理3.1即证。

定理1.3的证明：令$\epsilon =\frac{n\delta }{2\left(1+\delta \right)\left(n-k\right)}\cdot \frac{\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)}{\left(\begin{array}{c}n-1\\ k-1\end{array}\right)}$ 。下面我们证明$\mathcal{A},ℬ$ 中不存在$I,J$ 满足$e\left(I,J\right)\le \epsilon \left|I\right|\left|J\right|$ 。反证法假设$\mathcal{A},ℬ$ 中存在$I,J$ 满足$e\left(I,J\right)\le \epsilon \left|I\right|\left|J\right|$ 。根据定理3.1，我们可以得到，$\left|\mathcal{A}\right|\left|ℬ\right|\le {\tilde{\beta }}_{\epsilon }\left(KG\left(n,k\right)\right)$ ，即

$\left(1+\delta \right){\left(\begin{array}{c}n-1\\ k-1\end{array}\right)}^2<\left|\mathcal{A}\right|\left|ℬ\right|\le \frac{{\left(\begin{array}{c}n\\ k\end{array}\right)}^2{\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)}^2}{{\left(\begin{array}{c}n-k\\ k\end{array}\right)}^2-{\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)}^2+{\epsilon }^2{\left(\begin{array}{c}n\\ k\end{array}\right)}^2-2\epsilon \left(\begin{array}{c}n-k\\ k\end{array}\right)\left(\begin{array}{c}n\\ k\end{array}\right)}$ ,

不等式两边同时除以${\left(\begin{array}{c}n-1\\ k-1\end{array}\right)}^2$ ，可得

$1+\delta <\frac{\frac{n^2}{k^2}{\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)}^2}{{\left(\begin{array}{c}n-k\\ k\end{array}\right)}^2-{\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)}^2+{\epsilon }^2{\left(\begin{array}{c}n\\ k\end{array}\right)}^2-2\epsilon \left(\begin{array}{c}n-k\\ k\end{array}\right)\left(\begin{array}{c}n\\ k\end{array}\right)}$ ,

不等式右边分子分母同时除以${\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)}^2$ ，可得

$1+\delta <\frac{\frac{n^2}{k^2}}{{\left(\frac{n-k}{k}\right)}^2-1+{\epsilon }^2\frac{{\left(\begin{array}{c}n\\ k\end{array}\right)}^2}{{\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)}^2}-\frac{2\epsilon \left(n-k\right)}{k}\frac{\left(\begin{array}{c}n\\ k\end{array}\right)}{\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)}}$ .

不妨令$\epsilon =\frac{\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)}{\left(\begin{array}{c}n-1\\ k-1\end{array}\right)}\eta$ ，代入上式可得$1+\delta <\frac{\frac{n^2}{k^2}}{\frac{n^2-2nk}{k^2}+\frac{n^2}{k^2}{\eta }^2-\frac{2n\left(n-k\right)}{k^2}\eta }$ ，化简可得$\eta >\frac{n\delta }{2\left(1+\delta \right)\left(n-k\right)}$ ，于是

$\epsilon >\frac{n\delta }{2\left(1+\delta \right)\left(n-k\right)}\cdot \frac{\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)}{\left(\begin{array}{c}n-1\\ k-1\end{array}\right)}$ ,

这与$\epsilon =\frac{n\delta }{2\left(1+\delta \right)\left(n-k\right)}\cdot \frac{\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)}{\left(\begin{array}{c}n-1\\ k-1\end{array}\right)}$ 矛盾。于是$\mathcal{A},ℬ$ 中不存在$I,J$ 满足$e\left(I,J\right)\le \epsilon \left|I\right|\left|J\right|$ 。

因此2-匹配的数量至少为

$\epsilon \left|\mathcal{A}\right|\left|ℬ\right|\ge \frac{n\delta }{2\left(1+\delta \right)\left(n-k\right)}\cdot \frac{\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)}{\left(\begin{array}{c}n-1\\ k-1\end{array}\right)}\cdot \left(1+\delta \right){\left(\begin{array}{c}n-1\\ k-1\end{array}\right)}^2=\frac{n\delta }{2\left(n-k\right)}\left(\begin{array}{c}n-1\\ k-1\end{array}\right)\left(\begin{array}{c}n-k-1\\ k-1\end{array}\right)$ .

4. 结语

本文主要通过对独立数$\alpha \left(G\right)$ 的概念进行推广，从而得到了Hoffman界的推广，并将其应用于Kneser图中得到了两个重要结论。对于极图的构造仍需要后续进一步研究。

基金项目

国家自然科学基金(12471316)。

NOTES

^*通讯作者。