Recall:
Theorem: (Hoffman) $G$ d-正则，则：
$$ \alpha (G)\le \cdot \frac{-\lambda_n}{\lambda_1 -\lambda_n} .$$Hoffman 定理应用
EKR定理
Theorem: (Erdos-Ko-Rado) $f$ 是 k-uniform intersecting family, 则 $|f|\le {n-1\choose k-1}$，取等当且仅当所有集合都包含同一个元素。
Definition: (Kneser graph) $K(n,k)$ 点集： ${[n] \choose k}$，边集： $A \sim B$ iff $A \cap B=\emptyset$
Remark: Kneser graph 的独立集 $\leftrightarrow$ 一个 intersecting family.
EKR 定理 $\leftrightarrow$ 只需证明 $\alpha(K(n,k))\le {n-1\choose k-1}$
Theorem: (9.4.3 in GTM207) $K(n,k)$ 的所有特征值形如：
$$ (-1)^j {n-k-j \choose k-j} \text{ 重数为 } {n \choose j}- {n\choose j-1} .$$从而 $\lambda_1={n-k\choose k}, \lambda_n=-{n-k-1\choose k-1}$，带入 Hoffman 不等式即可证明
Petersen graph 的特征值
Note: $K(5,2)$ 是 Petersen graph
由前面定理可知其特征值为 $3^{(1)},1^{(5)},(-2)^{(4)}$ （括号内是重数）
能否不用前面定理，直接直接算特征值？
Note: $K(5,2)$ is $\{K_{3},C_{4}\}$-free
令 $A\coloneqq A(K(5,2))$，
$$ A^2(i,j)=\begin{cases} 3 & i=j\\ 0 & i\sim j\\ 1 & \text{otherwise} \end{cases} \implies A^2=2I+J-A .$$设 $\lambda \neq 3$ 是 $A$ 的特征值，$x$ 是对应的特征向量，则：
$$ A \mathbf{x}=\lambda \mathbf{x}, \mathbf{x} \cdot \mathbf{1}=0 .$$从而：
$$ \lambda ^2 \mathbf{x}=A^2 \mathbf{x}=(2I+J-A)\mathbf{x}=(2-\lambda )\mathbf{x}, \lambda =1 \text{ or } -2 .$$由上述证明，知道 $3$ 的重数为 $1$，（否则有其他垂直于 $\mathbf{1}$ 的特征向量，不满足上式）。
随后，用 trace 来算重数（$1$ 重数为 $a$，$-2$ 重数为 $b$）：
$$ \begin{aligned} &\implies 0=\text{tr}(A)=\sum \lambda_i=3+a+(-2)b\\ &\implies\begin{cases} a+b=9\\ 3+a-2b=0 \end{cases}\implies a=5,b=4. \end{aligned} $$划分 $K_{10}$
- $K(5,2)$ 是 3-正则的
- $K_{10}$ 是 9-正则的
Theorem: $K_{10}$ 不能分解为三个 $K(5,2)$
Proof: 假设能分解，令 $P_{1},P_{2},P_{3}$ 是三个子图的邻接矩阵。则 $P_{1}+P_{2}+P_{3}=J-I$。
令 $V_{1}$ 是 $P_{1}$ 的特征值 $1$ 张成的特征空间，$V_{2}$ 同理。
由于特征值 $1$ 重数为 $5$，因此 $\operatorname{dim}(V_{1})=\operatorname{dim}(V_{2})=5$，但是因为他们都与 $\mathbf{1}$ 垂直，而空间总的维数只有 $10$，因此他们不可能相互垂直。
从而 $\exists \mathbf{x} \in V_{1} \cap V_{2}$，并且
$$ \begin{cases} \mathbf{x} \cdot \mathbf{1}=0\\ P_{1}\mathbf{x}=\mathbf{x}\\ P_{2}\mathbf{x}=\mathbf{x} \end{cases} .$$则 $(P_{1}+P_{2}+P_{3})\mathbf{x}=(J-I)X=-\mathbf{x}$，另一方面 $LHS=2 \mathbf{x}+P_{3} \mathbf{x}$ 推出 $-3$ 是 $P_{3}$ 特征值，矛盾
Moore bound & Cages
典！
Definition: (Girth) 图的 girth 是最小的环的长度
Theorem 1: $\operatorname{girth}(G)\ge 5$，则 $|V(G)|\ge 1+d+d(d-1)$
Theorem: (Moore Bound) $G$ d-regular, $\operatorname{girth}(G)\ge 2k-1$，则 $|V(G)|\ge 1+d+\sum_{j=1}^{k-1} d(d-1)^j$
Cage thm
Theorem: (Cage) Theorem 1 不等式能取等仅当 $d=\{3,7,57\}$
其中 $3,7$ 有构造，$57$ 未知
Proof: 由于取等时图的性质，有：
$$ A^2=dI+J-I-A .$$假设 $\lambda \neq d$ 是 $A$ 的特征值，$x$ 是对应的特征向量，则：
$$ \begin{aligned} &\lambda^2 \mathbf{x}=A^2 \mathbf{x}=(d-1-\lambda )\mathbf{x}\\ &\implies \lambda ^2=d-1-\lambda \implies \lambda =\frac{1\pm \sqrt{4d-3}}{2} \end{aligned} .$$设 $\lambda_2,\lambda_3$ 重数为 $a,b$，则：
$$ \begin{aligned} \begin{cases} a+b=|V(G)|-1=d^2\\ 0=\operatorname{tr}(A)=d+a\lambda_2+b\lambda_3 \end{cases}\\ \implies (a-b) \sqrt{4d-3}=d^2-2d \end{aligned} .$$- $4d-3$ 不是平方数，则 $a=b, d=2$
- $4d-3$ 是平方数，令 $4d-3=s^2$
联立得到：
$$ s^{15}+s^4+6s^3-2s^2+(-3+a)s=15 .$$从而 $s \mid 15$, 从而 $s=\{1,3,5,15\}$