应用
Covering n-dim Cube by Afine hyper planes
Definition: $B_n\coloneqq \{0,1\}^n$, $H=\{\mathbf{x} \in \mathcal{R}^n \mid \mathbf{a}\cdot \mathbf{x}= b\}$
Theorem: $H_{1},H_{2}\ldots H_m$ 是 $\mathcal{R}^n$ 中的仿射超平面，并且覆盖了 $B_n$ 中除了 $0$ 点的所有点，则 $m\ge n$. Proof: 假设 $m < n$，构造多项式：
$$f(x_{1},\ldots x_n)\coloneqq \prod_{i=1}^{m} (\mathbf{a_i} \cdot \mathbf{x}-b_i)-\underbrace{\prod_{i=1}^{m} b_i \prod_{i=1}^{m}(1-x_i) }_{\text{使得 }x=0 \text{ 时 }f(x)=0} $$- $\deg f=n, \left[ \prod_{i=1}^{n} x_i \right] =(-1)^{n+1}\prod_{i=1}^{m} b_i\neq 0$
Note: 只有 $m < n$ ，$f$ 的最高次项才是后面这一项
- 令 $S_i\coloneqq \{0,1\}$ 得证。
Chevalle-Warning
Theorem: $p$ prime, $f_{1},\ldots f_n \in \mathcal{F}_P[x_{1},\ldots ,x_n]$，若 $\sum_{i=1}^{m} \deg f_i< n$，$f_{1},\ldots f_n$ 有公共根 $(c_{1},\ldots c_n)$，则他们还有另外的公共根
Proof: 假设他们只有 $(c_{1},\ldots c_n)$ 作为公共根，构造多项式：
$$ \begin{aligned} f(x_1,\ldots x_n)&\coloneqq \prod_{i=1}^{m} (1-f_i(x_{1},\ldots x_n)^{p-1})-\delta \prod_{j=1}^{n} \prod_{c: c\neq c_j, c \in \mathcal{F}_p} (x_j-c) \\ \delta &\coloneqq \frac{1}{\prod_{j=1}^{n} \prod_{c: c\neq c_j, c \in \mathcal{F}_p} (c_j-c)} \end{aligned} .$$Note:
$$ x^{p-1}=\begin{cases} 1 & x\neq 0\\ 0 & x=0 \end{cases} \pmod p .$$因此，
- $x=c$ 时，$f(x)=1-1=0$
- $x\neq c$ 时，$f(x)=\underbrace{0}_{\exists f_i(x)\neq 0}-\underbrace{0}_{\exists x_i \neq c_i}$
- $\deg f < n\cdot (p-1)$
- $S_{1}=S_{2}=\ldots = S_n= \mathcal{F}_p, t_i=p-1$, $\left[ \prod_{i=1}^{n} x_i^{p-1} \right] =\delta \neq 0$
Zero-Sum-Sets
Theorem: $p$ prime, 任何 $2p-1$ 个数，都包含大小为 $p$ 的子集，使得子集和为 $0 \pmod p$.
Proof 1: 设 $a_{1}\le a_{2}\le \ldots \le a_{2p-1}$
- 若 $\exists i, \text{s.t. } a_i=a_{i+p-1}$，则 $a_{i},\ldots a_{i+p-1}$ 即为所求
- 否则取 $S_i=\{a_i,a_{i+p-1}\}$ 由于 Cauchy-Davenport ，$|S_{1}+S_{2}+\ldots S_{p-1}|\ge p$，得证。
Proof 2:
构造 $f_{1},f_{2} \in \mathcal{F}_p[x_{1},\ldots x_{2p-1}]$
$$ f_{1}(x_{1},\ldots x_n)=\sum_{i=1}^{2p-1} x_i^{p-1}, f_{2}(x_{1},\ldots x_n)=\sum_{i=1}^{2p-1} a_i x_i^{p-1} .$$Note:
$$ x^{p-1}=\begin{cases} 1 & x\neq 0\\ 0 & x=0 \end{cases} \pmod p .$$
则 $\deg f_{1}+\deg f_2=2p-1\le 2p-1$，因为 $\mathbf{0}$ 是他们的公共根，由于所以他们还有另外的公共根，这一公共根 $x_i$ 的 support 对应一个符合要求的集合。
谱图论
基本内容：典，懒得写
Example:
- d-regular graph: $\lambda_{1}=d$
- $K_n$: $A=J_n-I_n$，$\lambda_{1}=n-1, \lambda_{2}=\ldots \lambda_n=-1$
- $K_{m,n}$: $\operatorname{rank}(A)=2, \lambda =\pm \sqrt{mn} ,(n-2)\text{个} 0$
- max deg $\Delta (G)$: $\lambda_{1}\le \Delta (G)$
Hoffman’s Thm
Theorem: $G$ 是 $d$-regular graph，则独立数 $\alpha (G)\ge \frac{n(-\lambda_n)}{\lambda_1-\lambda_{n}}$
Proof: 将 $A$ 特征分解, $\lambda_i$ 对应归一化的特征向量 $\mathbf{v}_i$，$\mathbf{v}_1=\frac{1}{\sqrt{n}}(1,1,\ldots 1)$
假设 $I$ 是独立集，$\mathbf{1}_I=\sum_{i=1}^{n} \alpha_i \mathbf{v}_i$。则：
$$ \begin{align} |I|&= \mathbf{1}_I\cdot \mathbf{1}_I=\sum_{i=1}^{n} \alpha_i^2 \\ \mathbf{1}_I \cdot v_1&=\alpha_1=\frac{1}{\sqrt{n}} |I|\\ \mathbf{1}_I^T A \mathbf{1}_I&=\sum_{i,j} \underbrace{a_{ij} \mathbf{1}_I(i) \mathbf{1}_I(j)}_{\text{由于独立集，不同时为} 1}=0 \notag \end{align} $$另一方面将 $\mathbf{1}$ 的分解形式带入：
$$ \begin{aligned} \mathbf{1}_I^T A \mathbf{1}_I&=(\sum \alpha_i \mathbf{v}_i)^T A(\sum \alpha_i \mathbf{v}_i)\\ &= \sum \lambda _i \alpha _i^2\ge \lambda_1 \alpha_{1}^2+\lambda_n(\sum_{i=2}^n \alpha_i^2) \\ &= \lambda_1 \frac{|I|^2}{n}+ \lambda_n (|I|-\frac{|I|^2}{n}). \tag*{(由 (2)(3))} \end{aligned} $$