关于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)$ .