10、代数方法

奇偶镇

问题：奇偶镇

一个小镇有 $n$ 个居民，它们希望建立一些俱乐部，按如下条件：

每个俱乐部有奇数个成员，且
任意两个俱乐部有偶数个共同成员。

它们可以建立多少个俱乐部？

例子

$A_{i} = {i}$ ， $i \in [n]$ ，给出 $n$ 个俱乐部；
$n$ 为偶数， $A_{i} = [n] ∖ {i}$ ，给出 $n$ 个俱乐部；
$n$ 为偶数， $A_{1} = [n] ∖ {1}$ , $A_{2} = [n] ∖ {2}$ ， $A_{i} = {1, 2, i}, i = 3, \dots, n$ ，给出 $n$ 个俱乐部。

问：是不是最多建立 $n$ 个？

定理：奇偶镇

$F \subset 2^{[n]}$ ，满足：

对任意 $A \in F$ ， $| A |$ 为奇；
对任意 $A \neq B \in F$ ， $| A \cap B |$ 为偶

则 $| F | \leq n$ 。

证明： 对任意 $A \in F$ ，定义指示向量：

1_{A} \in F_{2}^{n}, 1_{A} (i) = [i \in A] .

则这些条件在有限域 $F_{2}$ 下转化为

1_{A} \cdot 1_{A} = 1, 1_{A} \cdot 1_{B} = 0.

我们证明各 $1_{S}$ 线性无关。令 $α_{A} \in F_{2}$ ， $\sum α_{A} 1_{A} = 0$ ，则对任意 $B \in F$ 有

0 = 0 \cdot 1 = (\sum_{A \in F} α_{A} 1_{A}) \cdot 1_{B} = \sum_{A \neq B} α_{A} 1_{A} \cdot 1_{B} + α_{B} 1_{B} \cdot 1_{B} = α_{B} .

故 $α_{B} = 0$ 对任意 $B$ 成立。因此各 $1_{A}$ 线性无关。

综上，各 $1_{A}$ 的数量不超过 $\dim_{F_{2}} F_{2}^{n} = n$ 。即满足条件的集合 $A$ 的数量不超过 $n$ 。

第二证： 考虑矩阵

A = (\begin{matrix} 1_{A_{1}} \\ ⋮ \\ 1_{A_{m}} \end{matrix})

则

A A^{⊤} = (\begin{matrix} 1 \\ 1 \\ ⋱ \\ 1 \end{matrix}) .

由 $\rank A \geq \rank A A^{⊤} = \rank I = m$ ，故 $A$ 满秩，所以 $A$ 向量组无关。

在线性代数证明中，如下的两个事实是最好用的：

事实

线性无关向量组的向量数目不超过线性空间的维数；
$\rank (A B) \leq \rank (A) \rank (B)$ 。

练习：奇偶镇推广

考虑 $m$ 个红俱乐部 $R_{1}, \dots, R_{m} \subset [n]$ ， $m$ 个蓝俱乐部 $B_{1}, \dots, B_{m} \subset [n]$ ，使得

$| R_{i} \cap B_{i} |$ 为奇；
$| R_{i} \cap B_{j} |$ 为偶， $i \neq j$ ．

证明 $m \leq n$ ；特别地，若第二个条件弱化为对所有 $i < j$ 成立，则同样的结论仍然成立．

证明： 我们直接证明第二问．在 $F_{2}^{n}$ 上做．对 $X \in [n]$ ，令 $I_{X} = (I_{1 \in X}, I_{2 \in X}, \dots, I_{n \in X})$ ．定义矩阵

M_{1} = (\begin{matrix} I_{R_{1}} \\ ⋮ \\ I_{R_{m}} \end{matrix}), M_{2} = (I_{B_{1}}, \dots, I_{B_{m}}) .

则 $\rank M_{1} \leq n$ ， $\rank M_{2} \leq n$ ．另一方面，由题知 $I_{R_{1}} \cdot I_{B_{1}} = 1$ ， $I_{R_{i}} \cdot I_{B_{j}} = 0$ （ $i > j$ ），于是

M_{1} M_{2} = (\begin{matrix} 1 & 0 \\ 1 \\ ⋱ \\ * & 1 \end{matrix})

满秩．因此 $\rank M_{1} M_{2} \leq min {\rank M_{1}, \rank M_{2}} \leq n$ ．

练习

令 $m, n$ 为正整数， $m \geq n + 1$ ，则对任意 $[n]$ 的子集族 $A_{1}, \dots, A_{m}$ ，都存在下标集 $I_{1}, I_{2} \subset [m]$ 使得 $I_{1} \cap I_{2} = \emptyset$ ， $I_{1} \cup I_{2} \neq \emptyset$ ，且

⋃_{i \in I_{1}} A_{i} = ⋃_{i \in I_{2}} A_{i} .

证明： 若某个 $A_{i}$ 为空集，则

I_{1} = {i}, I_{2} = \emptyset

满足条件．否则，对每个 $A_{i}$ ，记 $v_{i}$ 为其指示向量，则这些向量均不为0．由 $m \geq n + 1$ ，这些向量线性相关，因此存在互不相交的下标集 $I_{1}, I_{2}$ 使得

\sum_{i \in I_{1}} α_{i} v_{i} = \sum_{i \in I_{2}} α_{i} v_{i}, α_{i} > 0, i \in I_{1} ⊔ I_{2} .

特别地，对第 $j$ 个位置，有

\sum_{i \in I_{1}} α_{i} 1_{A_{i}} (j) = \sum_{i \in I_{2}} α_{i} 1_{A_{i}} (j) .

由 $α_{i}$ 为正，两边为 $0$ 当且仅当所有的 $1_{A_{i}} (j)$ 均为0．在组合学语言中，这表明 $j \in ⋃_{i \in I_{1}} A_{i}$ 当且仅当 $j \in ⋃_{i \in I_{2}} A_{i}$ ．证毕．

偶奇镇

定理：偶奇镇

令 $F \subset 2^{[n]}$ ，满足：

$| A |$ 偶；
$| A \cap B |$ 奇。

则 $| F | \leq n$ 。

我们先全出一个弱一点的结论：

引理：弱结论

满足这一条件的 $F$ 满足 $| F | \leq n + 1$ 。

证明： 往 $F$ 中的每一个集合 $A$ 加入一个新元素 $n + 1$ ，得到新集族 $F^{*}$ 。则 $F^{*}$ 是奇偶镇。

原定理的证明： 只需证明 $| F | \neq n + 1$ 。反设 $F = {A_{1}, \dots, A_{n + 1}}$ ，则对任意 $1 \leq i \leq n + 1$ ，定义 $1_{A} \in F_{2}^{n}$ 同上。则这些向量在 $F_{2}^{n}$ 中线性相关，因此存在非全零的 $α_{i}$ 使得

\sum_{i = 1}^{n + 1} α_{i} 1_{A_{i}} = 0.

由偶奇镇假设，我们有

{\begin{cases} 1_{A} \cdot 1_{A} = 0; \\ 1_{A} \cdot 1_{B} = 1. \end{cases}

因此，我们有

0 = 0 \cdot 1_{A_{j}} = (\sum_{i = 1}^{n + 1} α_{i} 1_{A_{i}}) \cdot 1_{A_{j}} = \sum_{i = 1}^{n + 1} α_{i} - α_{j} .

故 $α_{j} = \sum_{i = 1}^{n + 1} α_{i}$ ，因此全体 $α_{i}$ 均相等。但其非全零，故全1，这说明 $1 = n + 1$ ，即 $n$ 偶。** $n$ 偶的结论非常重要！

然而，另一方面，我们有

\sum_{i = 1}^{n + 1} 1_{A_{i}} = 0.

考虑 $F^{c} = {A^{c} : A \in F}$ ，则 $F^{c}$ 也是偶奇镇（ $| A^{c} | = n - | A |$ 偶）， $| A^{c} \cap B^{c} | = n - | A \cup B | = n - | A | - | B | + | A \cap B |$ （奇）），同样有

\sum_{i = 1}^{n + 1} 1_{A_{i}^{c}} = 0.

于是 $0 = \sum + \sum^{c} = (n + 1) 1 = 1$ ，矛盾！

有一个更好的界是

定理：偶奇镇的深化

若 $F \subset 2^{[n]}$ 是偶奇镇，则

当 $n$ 奇时， $| F | \leq n$ ；
当 $n$ 偶时， $| F | \leq n - 1$ 。

定理：偶偶镇

若 $F \subset 2^{[n]}$ 是偶偶镇，即

$| A |$ 偶；
$| A \cap B |$ 偶。

则 $| F | \leq 2^{n / 2}$ 。

证明： 设出指示向量 $1_{A} \in F_{2}^{n} : A \in F$ ，由题知

$1_{A} ⊥ 1_{A}$ ；
$1_{A} ⊥ 1_{B}$ .
因此 $W := \span {1_{A} : A \in F} \subset W^{⊥}$ ，故 $\dim W \leq \dim W^{⊥}$ 。但 $\dim W + \dim W^{⊥} = n$ ，于是 $\dim W \leq \frac{n}{2}$ ，即 $| W | \leq 2^{\dim W} \leq 2^{n / 2} .$

Fisher 不等式

定理：Fisher 不等式

对固定的 $k$ ，令 $F \subset 2^{[n]}$ 满足 $| A \cap B | = k$ ，对任意 $A \neq B \subset F$ . 则 $| F | \leq n$ 。

证明： 对每个 $A \in F$ ，定义指示向量 $1_{A} \in R^{n}$ 。则对任意 $A \neq B \in F$ ， $1_{A} \cdot 1_{B} = k$ 。和从前一样，我们说明各 $1_{A}$ 在 $R^{n}$ 是线性无关的。

考虑线性组合 $\sum_{A \in F} α_{A} 1_{A} = 0$ ， $\forall α_{A} \in R$ 。则

\begin{aligned} 0 & = {(\sum_{A \in F} α_{A} 1_{A})}^{2} \\ = \sum_{A \in F} α_{A}^{2} 1_{A} \cdot 1_{A} + \sum_{A \neq B} α_{A} α_{B} 1_{A} \cdot 1_{B} \\ = \sum_{A \in F} α_{A}^{2} | A | + k \cdot \sum_{A \neq B} α_{A} α_{B} \\ = k {(\sum_{A \in F} α_{A})}^{2} + \sum_{A \in F} α_{A}^{2} (| A | - k) . \end{aligned}

注意到每个 $A$ 都至少含 $k$ 个元素，这给出 $\sum_{A \in F} α_{A}^{2} (| A | - k) \geq 0$ ，故 $k {(\sum_{A \in F} α_{A})}^{2} \leq 0$ ，因此两个项都等于 $0$ 。这说明 $\sum_{A \in F} α_{A} = 0$ ，且 $α_{A}^{2} (| A | - k) = 0$ 对任意 $A \in F$ 成立。

然而，由于 $| A \cap B | = k$ 对 $A \neq B$ 成立，至多有一个集合为 $k$ 元集。若存在这样的集合，记其为 $A^{*}$ ，则对任意 $A \in F ∖ {A^{*}}$ 有 $α_{A} = 0$ 。但 $\sum α = 0$ ，故全体 $α = 0$ ，这就给出了线性无关性，从而 $| F | \leq n$ 。证毕。

现在，我们来考虑 Fisher 不等式的一些应用。

定理（De Brujin-Erdos）

$P$ 为 $R^{2}$ 中的 $n$ 点集，则要么其共线，要么其构成 $n$ 条线。

证明： 令 $L$ 为这 $n$ 个点定义的直线族。我们说明要么 $| L | = 1$ ，要么 $| L | \geq | P | = n$ 。

对每个点 $x_{i} \in P$ ，定义分划 $L_{i} := {l \in L : l ∋ x_{i}}$ 。注意到对 $i \neq j$ ， $| L_{i} \cap L_{j} | = 1$ ；同时若存在 $i \neq j$ 使 $L_{i} = L_{j}$ ，则 $P$ 中所有点共线。因此，要么 $| L | = 1$ ，此时所有点共线；要么对每两个点 $x_{i}, x_{j} \in P$ ， $L_{i} \neq L_{j}$ 。

假设后者成立，令 $F = {L_{i} : x_{i} \in P} \subset 2^{L}$ ，即全体直线族分划的集族。则

L_{i} \cap L_{j} = {直线 i j}, | L_{i} \cap L_{j} | = 1 =: k .

满足 Fisher 不等式条件，故 $| F | \leq | L |$ 。但 $| F | = | P | = n$ ，证毕！

Fisher 不等式的第二种应用是显式构造 Ramsey 数 $R (k + 1, k + 1)$ 的一个界——虽然这个界比先前通过概率方法证明的一个界还要弱。

引理

令 $G$ 为图，满足：

$V (G) \in (\binom{[k]}{3})$ ，即顶点集为三元组；
$A B \in E (G)$ 当且仅当 $| A \cap B | = 1$ 。

则 $G$ 不包含任意一个 $k + 1$ 大小的团或独立集。

证明： 考虑 $G$ 中的最大团，如用顶点 $A_{1}, A_{2}, \dots, A_{m} \in (\binom{[k]}{3}) \subset 2^{[k]}$ 及 $| A_{i} \cap A_{j} | = 1$ 定义。由 Fisher 不等式，我们有 $m \leq k$ 。

现在，考虑 $G$ 中的最大独立集，如由 $B_{1}, B_{2}, \dots, B_{t} \in (\binom{[k]}{3})$ 定义。注意到 $| B_{i} | = 3$ 为奇数且 $| B_{i} \cap B_{j} | = 0$ 或 $2$ 为偶数。由奇偶镇定理， $t \leq k$ 。

推论

$R (k + 1, k + 1) > (\binom{k}{3}) .$

1-距离问题

给定 $R^{2}$ 上的 $n$ 个点，求距离 $1$ 的点对数最大值。

定理

点对数最大值至多为 $O (n^{3 / 2})$ 对。

证明： 定义图 $G$ ：对点 $a, b$ ， $a b \in E (G)$ 当且仅当 $d (a, b) = 1$ 。

我们证明 $G$ 无 $K_{2, 3}$ 。注意到 $a$ 的邻居必在以 $a$ 为中心、半径 $1$ 的圆上，任意如此的两个圆只能交于两点，因此 $G$ 无 $K_{2, 3}$ 。

\begin{document}
\begin{tikzpicture}
\fill[black] (0,0) circle (.05) node[left] {$p_1$};
\fill[black] (4,0) circle (.05) node[right] {$p_2$};
\draw[help lines] (0,0) circle (2.5);
\draw[help lines] (4,0) circle (2.5);
\fill[black] (2,1.5) circle (.05) node[left] {$q_1$};
\fill[black] (2,-1.5) circle (.05) node[left] {$q_2$};
\fill[black] (2,-3) circle (.05) node[left] {$q_3????$};
\draw (0,0) -- (2,1.5);
\draw (0,0) -- (2,-1.5);
\draw (4,0) -- (2,1.5);
\draw (4,0) -- (2,-1.5);
\draw[dashed] (0,0) -- (2,-3);
\draw[dashed] (4,0) -- (2,-3);
\draw[red] (-.5,.5) rectangle (4.5,-.5); 
\draw[blue] (1.5,2) rectangle (2.5,-3.5);
\end{tikzpicture}
\end{document}

因此，我们有

e (G) \leq ex (n, K_{2, 3}) = O (n^{3 / 2}) .

Erdos 的Open Problem

是否可以找到 $n^{1 + ε}$ 个点组成的 1-距离对子？

一个对偶问题是：是否 $R^{2}$ 中任意 $n$ 个点都包含至多 $n^{1 + O (1 / \log \log n)}$ 个1-距离对子？这也是Open 的。

问题

$R^{n}$ 中，两两间距离为 1 的点集点数最大值是多少？

定理

这样的点数至多为 $n + 1$ 。

证明： 这样的构造当然存在（ $R^{n}$ 中超正 $n + 1$ 面体）。现在考虑这些点的一个集合，假设有 $m + 1$ 个点，只需证明 $m < n$ 。不妨将其中一个点设为 $0$ ，另一些点设为向量 $v_{1}, \dots, v_{m} \in R^{n}$ 。则

$v_{i} \cdot v_{i} = 1$ ；
$v_{i} \cdot v_{j} = \frac{1}{2}$ 。（注意 $v_{i}, v_{j}, v_{j} - v_{i}$ 构成正三角形）

令 $A = (\begin{matrix} v_{1} \\ v_{2} \\ ⋮ \\ v_{m} \end{matrix})$ ，则 $A \cdot A^{⊤} = (\begin{matrix} 1 & 1 / 2 & \dots & 1 / 2 \\ 1 / 2 & 1 & \dots & 1 / 2 \\ ⋮ & ⋮ & ⋮ \\ 1 / 2 & 1 / 2 & \dots & 1 \end{matrix}) .$ 注意 $det (A A^{⊤}) \neq 0$ ，故 $A$ 的各行线性无关，从而 $m \leq n$ 。

多项式空间法

引理：三角准则（Triangular Criterion）

对 $i \in [n]$ ，令 $f_{i} : Ω \to F$ 为多项式，这里 $F$ 是域。如果存在元素 $v_{i} \in Ω$ 使得

{\begin{cases} f_{i} (v_{i}) \neq 0; \\ f_{i} (v_{j}) = 0, \forall j < i . \end{cases}

则各 $f_{i}$ 在其张成的线性空间中线性无关。

定义：2-距离集合

$R^{n}$ 中的点集，两两之间距离不是 $c$ 就是 $d$ 。（“两种距离”）

定理

$R^{n}$ 中的2-距离集至多有 $\frac{(n + 1) (n + 4)}{2}$ 个点。

证明： 令 $A = {a_{1}, \dots, a_{m}}$ 为 ${c, d} - 2$ 距离点集。对任意 $i \in [m]$ ，定义

f_{i} (x) = (∥ x - a_{i} ∥^{2} - c^{2}) (∥ x - a_{i} ∥^{2} - d^{2}), x \in R^{n} .

则我们有

{\begin{cases} f_{i} (a_{i}) = c^{2} d^{2} \neq 0; \\ f_{i} (a_{j}) = (∥ a_{i} - a_{j} ∥^{2} - c^{2}) (∥ a_{i} - a_{j} ∥^{2} - d^{2}) = 0, & j \neq i . \end{cases}

由三角准则，诸 $f_{i}$ 在 $S := span {f_{i}}_{1 \leq i \leq m}$ 中线性无关，i.e. $\dim S = m$ 。我们接下来界定 $\dim S$ 的界。

令 $x = (x_{1}, \dots, x_{n})$ ， $a_{i} = (a_{i 1}, \dots, a_{i n})$ 。注意到

\begin{aligned} f_{j} (x) & = (\sum_{i} (x_{i} - a_{j i})^{2} - c^{2}) (\sum_{i} (x_{i} - a_{j i})^{2} - d^{2}) \\ = (\sum_{i} x_{i}^{2} - 2 \sum_{i} x_{i} a_{j i} + \sum_{i} a_{j i}^{2} - c^{2}) (\sum_{i} x_{i}^{2} - 2 \sum_{i} x_{i} a_{j i} + \sum_{i} a_{j i}^{2} - d^{2}) . \end{aligned}

其可被表示为如下一组基的线性组合：

B = {{(\sum_{i} x_{i}^{2})}^{2}, x_{j} (\sum_{i} x_{i}^{2}), x_{i} x_{j}, x_{i}^{2}, x_{i}, 1} .

这组基共有 $1 + n + (\binom{n}{2}) + n + n + 1 = \frac{(n + 1) (n + 4)}{2}$ 个元素，证毕。

Remark

此方法可推广至 $k -$ 距离问题。

练习（A. Blokhuis）

把上述命题加强到 $(\binom{n + 2}{2})$ ．

证明： 在题目中定义的多项式

f_{i} (x) = (∥ x - a_{i} ∥^{2} - c^{2}) (∥ x - a_{i} ∥^{2} - d^{2}), i = 1, \dots, m

的基础上，再定义辅助多项式

1, x_{1}, x_{2}, x_{3}, \dots, x_{n} .

即常数及各坐标分量．我们证明 ${f_{i}}$ 及诸辅助多项式线性无关．注意这些辅助多项式在上题的 $B$ 中，因此也在空间中，这就给出

\begin{matrix} {f_{i}}_{i = 1}^{m} \cup {1, x_{1}, \dots, x_{n}} \subset \span B \\ \Rightarrow m + (n + 1) \leq \dim \span B \leq | B | = (\binom{n + 2}{2}) + n + 1. \end{matrix}

假设我们有

\sum_{i = 1}^{m} c_{i} f_{i} (x) + \sum_{i = 1}^{n} d_{i} x_{i} + C = 0.

取 $x = a_{j}$ ，得

\begin{matrix} (2) & c^{2} d^{2} c_{j} + \sum_{i = 1}^{n} d_{i} a_{j i} + C = 0, j = 1, 2, \dots, m . \end{matrix}

取 $x = k e_{j}$ ，这里 $e_{i}$ 是单位矩阵第 $j$ 列，得

\sum_{i = 1}^{m} c_{i} (k^{2} - 2 k a_{j i} + ∥ a_{j} ∥^{2} - c^{2}) (k^{2} - 2 k a_{j i} + ∥ a_{j} ∥^{2} - d^{2}) + k d_{i} + C = 0.

比较 $k^{4}$ ， $k^{3}$ 项系数得

\sum_{i = 1}^{m} c_{i} = 0, \sum_{j = 1}^{m} c_{i} a_{j i} = 0, \forall j = 1, \dots, d .

把 (2) 乘以 $c_{i}$ ，再对 $i$ 求和得

\sum_{i = 1}^{m} c_{i}^{2} + \sum_{i = 1}^{n} d_{i} \sum_{j = 1}^{m} c_{j} a_{j i} + C \sum_{j = 1}^{m} c_{j} = 0.

如上的两大行式子给出 $c_{i} = 0, \forall i = 1, \dots, m$ ．同时也有 $C = d_{i} = 0$ ．证毕．

问题：s-距离集

令 $m (n, s)$ 为 $R^{n}$ 中点数最大值：两两之间的距离取到至多 $s$ 个值．证明

(\binom{n + 1}{s}) \leq m (n, s) \leq (\binom{n + s + 1}{s}) .

证明： 下界．取 $R^{n}$ 中的单形，各顶点为 $v_{1}, \dots, v_{n + 1}$ ．取

S = {w_{I} = \frac{1}{s} \sum_{i \in I} v_{i} : I \in (\binom{[n + 1]}{s})} .

则 $| S | = (\binom{n + 1}{s})$ ，且对不同的 $I, J$ ，有 $∥ w_{I} - w_{J} ∥$ 只与 $| I \cap J |$ 有关，故只取至多 $s$ 个不同值．因此 $m (n, s) \geq (\binom{n + 1}{s})$ ．

上界．令 $X = {a_{1}, \dots, a_{m}} \subset R^{n}$ 只取 $s$ 个值 $δ_{1}, \dots, δ_{s}$ ．令

F (x, y) = \prod_{t = 1}^{s} (∥ x - y ∥^{2} - δ_{t}^{2}) .

令 $f_{i} (x) = F (a_{i}, x)$ ，则每个 $f_{i}$ 是次数至多为 $2 s$ 的多项式．但是这里计数是困难的，需要一点强词夺理．考虑

f_{i} (x) = \prod_{t = 1}^{s} (∥ x ∥^{2} - 2 ⟨ x, a_{i} ⟩ + ∥ a_{i} ∥^{2} - δ_{t}^{2}) = \prod_{t = 1}^{s} (\sum_{i = 1}^{n} x_{i}^{2} - 2 \sum_{j = 1}^{n} a_{i j} x_{j} + ∥ a_{i} ∥^{2} - δ_{t}^{2}) .

如果直接计数会出来 $2 s$ 次，这样张成的多项式空间是 $(\binom{n + 2 s}{2 s})$ 了，很难受．为了降低次数，令 $y_{0} = ∥ x ∥^{2}$ ，则 $f_{i}$ 视作以 $y_{0}, x_{1}, \dots, x_{n}$ 为变量的多项式时总次数为 $s$ ．而 $y_{0}, x_{1}, \dots, x_{n}$ 张成的多项式空间维数至多为 $(\binom{n + s + 1}{s})$ ．

最后，各 ${f_{i}}$ 线性无关：首先 $f_{i} (a_{i}) = \prod δ_{t}^{2} \neq 0$ ，其次 $f_{i} (a_{j}) = 0$ ．由三角准则知线性无关，故证毕．

L-相交系

定义：

L

-相交系

考虑子集 $L \subset {0, \dots, n}$ 。称族 $F \subset 2^{[n]}$ 是 L-相交的，若对任意 $A \neq B \in F$ ， $| A \cap B | \in L$ 。

定理（Frankl-Wilson）

若 $F \subset 2^{[n]}$ 为 $L -$ 相交系，则 $F | \leq \sum_{k = 0}^{| L |} (\binom{n}{k})$ 。

证明： 令 $F = {A_{1}, \dots, A_{m}}$ ， $| A_{1} | \leq \dots \leq | A_{m} |$ 。对每个 $i \in [m]$ ，定义

f_{i} (x) : R^{n} \to R, x \mapsto \prod_{l \in L, l < | A_{i} |} (x \cdot 1_{A_{i}} - l) .

考虑指示向量 $1_{A_{1}}, 1_{A_{2}}, \dots, 1_{A_{m}}$ ，则我们有

$f_{i} (1_{A_{i}}) = \prod_{l \in L, l < | A_{i} |} (| A_{i} | - l) > 0$ ；
$f_{i} (1_{A_{j}}) = \prod_{l \in L, l < | A_{i} |} (| A_{i} \cap A_{j} | - l) = 0$ ,对任意 $j < i$ 。

这是因为 $l = | A_{i} \cap A_{j} | \in L$ ，且 $l < | A_{i} |$ 对某些 $l$ 成立（由 $j < i$ 时 $| A_{j} | < | A_{i} |$ ）。由三角准则，各 $f_{i}$ 线性无关。

接下来，我们定义一些新的多项式 ${\tilde{f}}_{i} (x)$ ，使得各多项式线性无关——但这些多项式位于一个“更好”的线性空间。注意到各 $1_{A_{j}}$ 为 $0 / 1$ 向量，令 ${\tilde{f}}_{i} (x)$ 为将 $f_{i} (x)$ 中各 $x_{j}^{k}$ 项都换成 $x_{j}$ 。注意到 ${\tilde{f}}_{i} (1_{A_{j}}) = f_{i} (1_{A_{j}})$ ，因此新定义的这些函数都是线性无关的，且 ${\tilde{f}}_{i} (x)$ 的各项是单项式 $\prod_{i \in I} x_{i}$ 之和， $I$ 为某种指标集。显然这样的单项式共有 $\sum_{k = 0}^{| L |} (\binom{n}{k})$ 个，这就给出了结论

| F | = | m | \leq \sum_{k = 0}^{| L |} (\binom{n}{k}) .

练习

令 ${A_{1}, \dots, A_{m}}$ 为 $[n]$ 中的 $L -$ 相交系，且各个 $A_{i}$ 大小恒为 $k$ ， $L \subset [k - 1] \cup {0}$ ，证明 $m \leq (\binom{n}{| L |})$ ．

证明： 令 $L = {l_{1}, \dots, l_{s}}$ ， $s = | L |$ ．对每个 $i \in [m]$ ，定义

f_{i} (x) = \prod_{t = 1}^{s} (x \cdot 1_{A_{i}} - l_{t}) .

对每个 $I \subset [n]$ ， $| I | \leq s - 1$ ，定义

g_{I} (x) = (\sum_{j = 1}^{n} x_{j} - k) \prod_{i \in I} x_{i} .

则 ${f_{i}}$ 、 ${g_{I}}$ 线性无关．具体来说，设

\sum_{i = 1}^{m} λ_{i} f_{i} + \sum_{| I | \leq s - 1} μ_{I} g_{I} = 0,

对 $x = 1_{A_{j}}$ 计算（ $i \neq j$ ），则 $f_{j} (1_{A_{j}}) = \prod_{t = 1}^{s} (k - l_{t}) \neq 0$ ， $g_{I} (1_{A_{j}}) = 0$ （因 $\sum_{j} x_{j} = k$ ）．因此 $λ_{j} = 0$ ， $\forall j$ ．

现在，假设 $\sum_{| I | \leq s - 1} μ_{I} g_{I} = 0$ ，我们对 $| I |$ 归纳证明 $μ_{I} = 0$ ．选定 $J \subset [n]$ 使得 $| J | \leq s - 1$ 最小且 $μ_{J} \neq 0$ ．计算关联向量 $1_{J}$ ：对任意 $I \subset J$ ， $g_{I} (1_{J}) = 0$ 除非 $I = J$ ．（因为 $\sum x_{j} = | J | \neq k$ ， $\forall | J | \leq s - 1 < k$ ）．于是 $0 = \sum μ_{I} g_{I} (1_{J}) = μ_{J} g_{J} (1_{J})$ ，但 $g_{J} (1_{J}) \neq 0$ ，矛盾．从而所有 $μ_{I} = 0$ ．

如上的多项式次数最多为 $s$ ，且限制在 $F_{2}^{n}$ 上均为多线性的，因此其位于 $\prod_{i \in I} x_{i}$ 中， $| I | \leq s$ ——这样的多项式空间大小为 $\prod_{t = 0}^{s} (\binom{n}{t})$ ．因此 $g_{I}$ 的数目为 $\sum_{t = 0}^{s - 1} (\binom{n}{t})$ ，故

m + \sum_{t = 0}^{s - 1} (\binom{n}{t}) \leq \sum_{t = 0}^{s} (\binom{n}{t}) .

故 $m \leq (\binom{n}{s}) = (\binom{n}{| L |})$ ．

定理

令 $p$ 为素数， $L \subset F_{p}$ ，令 $F \subset 2^{[n]}$ 满足

$| A | \notin L \mod p$ ，对任意 $A$ ；
$| A \cap B | \in L$ ，对任意 $A \neq B$ 。

则 $F | \leq \sum_{k = 0}^{| L |} (\binom{n}{k})$ .

证明： 所有操作在模 $p$ 下进行。令 $F = {A_{1}, \dots, A_{m}}$ ，令 $f_{i} (x) : F_{p}^{*} \to F_{p}$ 为

f_{i} (x) = \prod_{l \in L} (x \cdot 1_{A_{i}} - l) .

则

$f_{i} (1_{A_{i}}) \neq 0$ ；
$f_{i} (1_{A_{j}}) = \prod_{l \in L} (| A_{i} \cap A_{j} | - l) = 0$ ， $\forall i \neq j$ 。

于是 $f_{1}, \dots, f_{m}$ 在 $F_{p}^{n}$ 上线性无关。再作上述定理证明中一样的规换 $x_{j}^{k} \to x_{j}$ ，即证。

注意

这是奇偶镇或偶奇镇问题的一个推广。

定理（Frankl-Wilson）

对任意素数 $p$ ，存在一个 $n = (\binom{p^{3}}{p^{2} - 1})$ 阶图 $G$ ，使得其中的最大团和最大独立集的大小均不超过 $\sum_{i = 0}^{p - 1} (\binom{p^{3}}{i})$ 。

证明： 令 $G = (V, E)$ ，这里 $V = (\binom{[p^{3}]}{p^{2} - 1})$ 。对 $A, B \in V$ ，定义等价关系

A \sim_{G} B \Leftrightarrow | A \cap B | ≢ - 1 (\mod p) .

考虑由 $A_{1}, \dots, A_{m} \in (\binom{[p^{3}]}{p^{2} - 1})$ 构成的最大团。我们有

$| A_{i} \cap A_{j} | ≢ - 1 (\mod p)$ ， $\forall i \neq j$ 。
$| A_{i} | = p^{2} - 1 \equiv - 1 (\mod p)$ 。

对 $L = {0, 1, \dots, p - 2} \subset F_{p}$ 应用上面的定理，可得 $m \leq \sum_{i = 0}^{p - 1} (\binom{p^{3}}{i})$ 。

考虑最大的独立集 $B_{1}, \dots, B_{t}$ 。则我们有 $| B_{i} \cap B_{j} | = - 1 (\mod p)$ ， $\forall i \neq j$ ，这给出 $| B_{i} \cap B_{j} | \in {p - 1, 2 p - 1, \dots, p (p - 1) - 1} = L^{*}$ ， $| L^{*} | = p - 1$ 。因此 $B_{1}, \dots, B_{t}$ 是 $(\binom{[p^{3}]}{p^{2} - 1})$ 的一个 $L^{*} -$ 相交系。由第一个 Frankl-Wilson 定理，可得 $t \leq \sum_{i = 0}^{p - 1} (\binom{p^{3}}{t})$ ，证毕。

推论

$R (k + 1, k + 1) \geq k^{Ω (\log k / (\log \log k))} .$

证明： 由上述定理的证明过程，令 $k = \sum_{i = 0}^{p - 1} (\binom{p^{3}}{i})$ ，则 $R (k + 1, k + 1) > n$ 。我们有

k = \sum_{i = 0}^{p - 1} (\binom{p^{3}}{i}) \approx (\binom{p^{3}}{p}) \approx (p^{2})^{p} \approx p^{2 p}, n \approx {(\frac{p^{3}}{p^{2}})}^{p^{2}} \approx p^{p^{2}} .

这表明 $\log k \sim p \log p$ ， $\log \log k \sim \log p$ ，于是 $p \sim \frac{\log k}{\log \log k}$ 。故

n = (\binom{p^{3}}{p^{2} - 1}) \sim (p^{2 p})^{p / 2} \sim k^{p} = k^{Ω (\log k / (\log \log k))} .