Bóna · 枚举与解析组合学导论 · 第 6 章 极值组合学

6.2　超图Hypergraphs

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。

在上一节里，我们考察了在某种意义下达到极端（extremal）的图。一个图其实无非就是一些边（edge）的集合，换句话说，就是顶点集（vertex set）的若干个二元子集。

如果我们允许更大的子集，这个概念就可以被推广。这些由子集组成的新的集族，正是本节的主要研究对象。

定义 6.28 集合 \([n]\) 上的一个超图（hypergraph）是 \([n]\) 的若干个子集组成的集族。这个集族中的元素（它们本身是 \([n]\) 的子集）称为该超图的边（edges），而 \([n]\) 中的元素称为该超图的顶点（vertices）。

因此图只是超图的一种特殊情形，即每条边都恰好由两个顶点组成的特殊情形。超图也常被称为集系（set systems）或子集族（families of subsets）。人们常用花体字母（如 \(\mathcal{F}\)）来记它们。

在本节中，我们要寻找在某种意义下最优的超图，例如在给定条件下边数尽可能多的超图。对一个超图 \(\mathcal{F}\)，我们用 \(|\mathcal{F}|\) 表示 \(\mathcal{F}\) 的边数。

本节目标把“图”升级为“超图”：边不再只是两个点，而可以是任意大小的子集。核心问题是——当我们对边之间的“相交关系”施加限制时，超图最多能有多少条边？我们会先看“任意两条边都不互不相交”的情形，再加上“每条边大小都相同”的限制（\(k\)-一致超图），得到著名的 Erdős–Ko–Rado 定理，最后认识一种特别整齐的结构——向日葵。
普通图：边 = 两个点 超图：边 = 任意子集
左：普通图每条边圈住两个点。右：超图的一条边可以圈住 \(1,2,3,\dots\) 个点——一条边就是顶点集的一个子集。

6.2.1　两两相交的边构成的超图

定理 6.29 设 \(\mathcal{F}\) 是顶点集 \([n]\) 上的超图，且 \(\mathcal{F}\) 中不含两条互不相交的边。则 \[|\mathcal{F}|\le 2^{\,n-1}.\]
证明. 我们把 \([n]\) 的 \(2^n\) 个子集两两配成对：每个子集与它的补集（complement）配成一对。这样会得到 \(2^{n-1}\) 对。每一对都由两个互不相交的子集组成（一个集合与它的补集必然不相交），所以 \(\mathcal{F}\) 在每一对中最多只能含有一条边。这就证明了 \(\mathcal{F}\) 的元素个数不会超过这些对的数目，即 \(2^{n-1}\)。♦
例（\(n=3\) 把证明走一遍） 取 \([3]=\{1,2,3\}\)。它的 \(2^3=8\) 个子集按“集合 ↔ 补集”配成 \(2^{3-1}=4\) 对：
  1. \(\varnothing\) ↔ \(\{1,2,3\}\)
  2. \(\{1\}\) ↔ \(\{2,3\}\)
  3. \(\{2\}\) ↔ \(\{1,3\}\)
  4. \(\{3\}\) ↔ \(\{1,2\}\)
每一对里两个集合互不相交。若 \(\mathcal{F}\) 不能含两条不相交的边，那么每一对里它至多挑一个，故 \(|\mathcal{F}|\le 4=2^{3-1}\)。
∅ {1,2,3} {1} {2,3} {2} {1,3} {3} {1,2}
\(n=3\) 时的 4 对“集合 ↔ 补集”。虚线相连的两个集合互不相交，每对里最多入选一个，故边数 \(\le 4\)。

上面的证明并不太难。这或许会让人觉得，只要再多花点力气，就能把这个结果进一步改进。然而这种希望是落空的，下面的定理说明了这一点。

定理 6.30 在顶点集 \([n]\) 上存在一个有 \(2^{\,n-1}\) 条边的超图 \(\mathcal{F}\)，使得 \(\mathcal{F}\) 中没有两条边互不相交。
证明. 令 \(\mathcal{F}\) 为这样的超图：它的边恰好是 \([n]\) 中所有含顶点 \(1\) 的子集。♦

我们想指出，上述证明中定义的超图 \(\mathcal{F}\) 实际上比我们所需要的还要好。它不仅具有“任意两条边都相交”的性质，而且具有“全部边都有公共元素”的更强性质！（关于定理 6.30 的另一种证明，见习题 13。）

例（为什么含顶点 1 的子集恰有 \(2^{n-1}\) 个） 一个含顶点 \(1\) 的子集，相当于：先把 \(1\) 放进去，再在剩下的 \(n-1\) 个顶点 \(\{2,3,\dots,n\}\) 中任意决定“放或不放”。每个顶点有 \(2\) 种选择，故共 \(2^{n-1}\) 个子集。它们两两都含有 \(1\)，因此任意两条边都相交（公共元素至少是 \(1\)）。这恰好达到定理 6.29 的上界，说明上界 \(2^{n-1}\) 是不可改进的。
1 公共顶点
把“顶点 1”塞进每一条边，无论这些边其它部分如何，它们都因共享 \(1\) 而两两相交。这样的边共有 \(2^{n-1}\) 条。

现在可以提出一个问题：如果要求 \(\mathcal{F}\) 中任意两条边相交于至少 \(k\) 个元素（而不仅仅是至少一个元素），那么 \(\mathcal{F}\) 最多能有多大？此时读者可能会建议：把 \(\mathcal{F}\) 定义为 \([n]\) 中所有包含集合 \([k]\) 的子集组成的超图。这个族有 \(2^{\,n-k}\) 个元素，并且显然满足“两两交的大小 \(\ge k\)”这个条件。问题是：我们能不能做得更好？下面的构造表明，当 \(n\) 足够大时，确实可以。

例 6.31 设 \(k\) 使得 \(n+k\) 为偶数，令 \(\mathcal{F}\) 为顶点集 \([n]\) 上以“所有恰有 \((n+k)/2\) 个元素的子集”为边的超图。则 \(\mathcal{F}\) 中任意两条边相交于至少 \(k\) 个元素；并且当 \(n\) 足够大时，\(|\mathcal{F}|>2^{\,n-k}\)。
解. 确实，任意两条边合起来一共有 \(n+k\) 个元素（按重数计），而它们都装在只有 \(n\) 个元素的 \([n]\) 里，所以它们必须共享至少 \(k\) 个顶点。另一方面，\(\mathcal{F}\) 的边数是 \(\dbinom{n}{(n+k)/2}\)，我们要证明：当 \(n\) 足够大时， \[\tag{6.4}\binom{n}{(n+k)/2}>2^{\,n-k}.\] 首先注意，若 \(n=3k\)，则由斯特林公式（Stirling's formula，(1.13)）左边等于 \[\binom{3k}{k}\sim 6.75^{\,k}\sqrt{\frac{3}{2n\pi}},\] 而右边只是 \(4^{\,k}\)。其次注意，当 \(n\) 增加到 \(n+2\) 时，左边乘上的因子为 \(\dfrac{4(n+2)(n+1)}{(n+k+2)(n-k+2)}\)，而右边只是简单地乘上 \(4\)。对足够大的 \(n\)（例如 \(n=3k\)），左边的增长速率更大，因此 (6.4) 的左边始终保持大于右边。♦
为什么“两条边合起来 \(n+k\) 个元素”就保证交集 \(\ge k\)设两条边为 \(A,B\)，各有 \((n+k)/2\) 个元素。由容斥（即加法原理的差版）：\(|A\cap B|=|A|+|B|-|A\cup B|\)。而 \(A\cup B\subseteq[n]\)，所以 \(|A\cup B|\le n\)。于是 \[|A\cap B|\ge \tfrac{n+k}{2}+\tfrac{n+k}{2}-n=k.\] 这就是“两条等大的边必然相交于 \(\ge k\) 个元素”的来历。
例（用具体数字看 (6.4) 为什么成立） 取 \(k=2\)，比较 \(\dbinom{n}{(n+2)/2}\) 与 \(2^{\,n-2}\)（\(n\) 取偶数）：
  1. \(n=4\)：\(\binom{4}{3}=4\)，\(2^{2}=4\)。相等，还没超过。
  2. \(n=6\)：\(\binom{6}{4}=15\)，\(2^{4}=16\)。左边稍小。
  3. \(n=8\)：\(\binom{8}{5}=56\)，\(2^{6}=64\)。左边仍稍小。
  4. \(n=10\)：\(\binom{10}{6}=210\)，\(2^{8}=256\)。差距在缩小。
  5. \(n=14\)：\(\binom{14}{8}=3003\)，\(2^{12}=4096\)；\(n=18\)：\(\binom{18}{10}=43758\)，\(2^{16}=65536\)。
对 \(k=2\) 这个例子，二项式系数增长得不够快，要 \(k\) 较大、\(n\) 在 \(3k\) 附近时左边才反超——这正是书中取 \(n=3k\) 来论证“足够大”的原因。比较“每把 \(n\) 加 \(2\)”时两边的增长因子：右边乘 \(4\)，左边乘 \(\dfrac{4(n+2)(n+1)}{(n+k+2)(n-k+2)}\)，在 \(n=3k\) 附近约为 \(\dfrac{4\cdot 3k\cdot 3k}{4k\cdot 2k}=4.5>4\)，于是左边持续追上并最终超过右边。

现在让我们进一步收窄兴趣，去寻找其中每条边大小都相同的最优超图。这一类超图出现得如此频繁，以至于它有自己专门的名字。

定义 6.32 若超图 \(\mathcal{F}\) 的所有边都恰由 \(k\) 个顶点组成，则称 \(\mathcal{F}\) 为 \(k\)-一致的（\(k\)-uniform）。

首先，我们来寻找不含互不相交的边的大型 \(k\)-一致超图。正如对一般超图所做的那样，我们可以通过把某个固定元素放进 \(\mathcal{F}\) 的所有边中，来确保“非不相交”的条件得到满足。

命题 6.33 对一切正整数 \(k\in[n]\)，在顶点集 \([n]\) 上存在一个有 \(\dbinom{n-1}{k-1}\) 条边的 \(k\)-一致超图，它不含两条互不相交的边。
证明. 以“所有含顶点 \(1\) 的 \(k\) 元子集”为边的超图就具有所要求的性质。♦
例（数一数含顶点 1 的 \(k\) 元子集） 取 \(n=5,\ k=3\)。一个含 \(1\) 的 \(3\) 元子集 = \(\{1\}\) 再从 \(\{2,3,4,5\}\) 里选 \(2\) 个，故共 \(\binom{4}{2}=6\) 条边： \[\{1,2,3\},\{1,2,4\},\{1,2,5\},\{1,3,4\},\{1,3,5\},\{1,4,5\}.\] 它们两两都含 \(1\)，故两两相交。这里 \(\binom{n-1}{k-1}=\binom{4}{2}=6\)。

读者大概不会感到意外：我们讨论的这个简单构造再一次是最优的。虽然结论与定理 6.29 非常相似，但它的证明要难得多。

定理 6.34（Erdős–Ko–Rado 定理） 设 \(\mathcal{F}\) 是 \([n]\) 上的 \(k\)-一致超图，且不含两条互不相交的子集。则
  1. 当 \(2k\le n\) 时，\(\;|\mathcal{F}|\le\dbinom{n-1}{k-1}\)；
  2. 当 \(2k>n\) 时，\(\;|\mathcal{F}|\le\dbinom{n}{k}\)。

我们给出的证明归功于 Gyula O. H. Katona [48]，它比该定理的原始证明 [28] 简单得多。

证明. 第 (b) 部分是对的，因为我们可以取 \(\mathcal{F}\) 为 \([n]\) 的全体 \(k\) 元子集（此时任意两条边都相交是因为 \(2k>n\)，两个 \(k\) 元集不可能在 \(n\) 个元素里互不相交）。下面证第 (a) 部分。

把 \([n]\) 的元素想成 \(n\) 个不同的人，他们围着一张圆桌坐在编号为 \(0\) 到 \(n-1\) 的 \(n\) 把椅子上，如图 6.10 所示。

一旦座位排定，若在该排法中有 \(k\) 个人坐在 \(k\) 把连续的椅子上，我们就说他们在该排法中构成一个区块（block）。更精确地说，若 \(k\) 个人在某个排法中坐在椅子 \(a,a+1,\dots,a+k-1\) 上，我们就把他们称为该排法的区块 \(B_a\)。这里的加法是模 \(n\) 意义下的，也就是说 \(n+c=c\)。

0 1 2 n−1 a a+1 a+k
图 6.10　围着圆桌的椅子，编号 \(0\) 到 \(n-1\)。从椅子 \(a\) 起的 \(k\) 把连续椅子上的人构成区块 \(B_a\)（加法模 \(n\)）。

首先，我们断言：对任意给定的一种排法，\(\mathcal{F}\) 至多包含该排法的 \(k\) 个区块。事实上，设 \(B_a\in\mathcal{F}\)。那么 \(\mathcal{F}\) 中其余所有区块都必须与 \(B_a\) 相交，因此它们都必形如 \(B_{a+i}\) 或 \(B_{a-i}\)，其中 \(i\in[k-1]\)。这表明 \(\mathcal{F}\) 中至多有 \(2k-1\) 个区块——但这还不是我们承诺的结果。于是我们进一步指出：\(\mathcal{F}\) 甚至不能把这些区块全装下。事实上，对任意 \(j\in[k-1]\)，区块 \(B_{a-k+j}\) 与 \(B_{a+j}\) 互不相交，所以 \(\mathcal{F}\) 在它们当中至多含一个。这就证明了 \(\mathcal{F}\) 确实至多含 \(k\) 个区块。

例（\(n=8,\ k=3\)，区块为何至多 \(k=3\) 个） 设 \(B_a=\{a,a{+}1,a{+}2\}\) 入选。与它相交的连续三元块只能是把窗口左右各挪 \(1\) 或 \(2\) 格的那些。把 \(8\) 个区块按起点排开，与 \(B_a\) 相交的有 \(2k-1=5\) 个；再从中剔除互不相交的成对块，最终最多剩 \(3\) 个。
  1. 设 \(a=0\)，\(B_0=\{0,1,2\}\) 入选。
  2. 与 \(B_0\) 相交的块：\(B_6=\{6,7,0\},B_7=\{7,0,1\},B_0,B_1=\{1,2,3\},B_2=\{2,3,4\}\)，共 \(5\) 个。
  3. 但 \(B_6=\{6,7,0\}\) 与 \(B_2=\{2,3,4\}\) 不相交，故二者至多取一个；同理 \(B_7\) 与 \(B_1\) 也不相交。
  4. 于是最多保留 \(B_0\) 以及每对里各一个，合计 \(\le 3=k\) 个区块。

现在我们来计数所有可能的对 \((p,B)\)，其中 \(p\) 是这 \(n\) 个人围桌而坐的一种排法，\(B\) 是该排法中一个属于 \(\mathcal{F}\) 的区块。设这种对的总数为 \(P\)。

先按排法来数。我们刚刚看到，每种排法至多有 \(k\) 个属于 \(\mathcal{F}\) 的区块。因此 \[\tag{6.5}P\le k\cdot n!.\]

再按区块来数。若 \(B\in\mathcal{F}\)，要把 \(B\) 的人安排成排法 \(p\) 中的一个区块：先用 \(n\) 种方式选定区块的起始椅子 \(a\)；然后把 \(B\) 的 \(k\) 个人安排到椅子 \(a,a+1,\dots,a+k-1\) 上，有 \(k!\) 种方式；最后把其余 \(n-k\) 个人安排到其余椅子上，有 \((n-k)!\) 种方式。由于对每个 \(B\in\mathcal{F}\) 都能这样做，于是 \[\tag{6.6}P=|\mathcal{F}|\cdot n\cdot k!\cdot(n-k)!.\]

比较 (6.5) 与 (6.6)，得到 \[|\mathcal{F}|\cdot n\cdot k!\cdot(n-k)!\le k\cdot n!,\] \[|\mathcal{F}|\le\frac{k}{n}\cdot\binom{n}{k}\le\binom{n-1}{k-1}.\] ♦

最后一步的代数为什么对用 \(\dbinom{n}{k}=\dfrac{n!}{k!\,(n-k)!}\) 把不等式整理：
  1. 由 (6.5)、(6.6)：\(|\mathcal{F}|\cdot n\cdot k!\,(n-k)!\le k\cdot n!\)。
  2. 两边同除 \(n\cdot k!\,(n-k)!\)：\(|\mathcal{F}|\le \dfrac{k\cdot n!}{n\cdot k!\,(n-k)!}=\dfrac{k}{n}\binom{n}{k}\)。
  3. 再用恒等式 \(\dfrac{k}{n}\dbinom{n}{k}=\dbinom{n-1}{k-1}\)（把 \(\dfrac{k}{n}\) 乘进去：\(\dfrac{k}{n}\cdot\dfrac{n!}{k!(n-k)!}=\dfrac{(n-1)!}{(k-1)!(n-k)!}\)）。
即时自测如果你认为自己理解了这个证明，可以测一测：请找出证明中究竟在哪一步用到了条件 \(2k\le n\)。（提示：区块 \(B_{a-k+j}\) 与 \(B_{a+j}\) 真的“互不相交”需要它们在圆周上不绕回来重叠，这正需要 \(2k\le n\)。）

我们想指出该证明的一个重要特征，它在将来会反复有用。证明的关键，是去计数对 \((p,B)\)——一次按排列数，一次按区块数。这种技巧——计数特定的“对”，先按其第一分量数一次，再按其第二分量数一次，然后比较两个结果——是一件简单却强大的工具。

Erdős–Ko–Rado 定理有许多变体。下面这个变体（以更一般的形式）由 Béla Bollobás [11] 证明。

定理 6.35 设 \(\mathcal{F}\) 是 \([n]\) 上的 \(k\)-一致超图，有 \(2m\) 条边，且其所有边可以列成 \(X_1,X_2,\dots,X_m\) 与 \(Y_1,Y_2,\dots,Y_m\)，使得 \(X_i\cap Y_j=\varnothing\) 当且仅当 \(i=j\)。则 \[|\mathcal{F}|\le\binom{2k}{k}.\]

可以这样来理解这个问题：一位橄榄球教练有 \(n\) 名队员，想让他们组成各种队伍，进行 \(m\) 场互相对抗的短局。每一局里，一支队只打进攻，另一支队只打防守。同一局中没有队员能同时在两队（这就是限制 \(X_i\cap Y_i=\varnothing\) 的来历）。此外，由于这是一位有组合学倾向的教练，他还要求：除了当前对手之外，没有任何一支进攻队与某支防守队完全不相交；反之亦然，除了当前对手之外，没有任何一支防守队与某支进攻队完全不相交。（恐怕没有几位教练会担心违反最后这个条件，但这一位会。）

注意，这个上界甚至不依赖于 \(n\)。无论 \(n\) 有多大，最优的 \(\mathcal{F}\) 的规模都不会增长。这说明我们这里处理的是比 Erdős–Ko–Rado 定理强得多的限制。

证明（定理 6.35）. 我们计数满足下述条件的对 \((p,i)\) 的个数 \(P\)：\(p=p_1p_2\cdots p_n\) 是一个 \(n\)-排列，\(i\in[m]\)，且在 \(p\) 中 \(X_i\) 的所有元素都排在 \(Y_i\) 的所有元素之前。

先按下标 \(i\in[m]\) 来数。固定 \(i\)，则 \(X_i\) 与 \(Y_i\) 也固定。我们称两个排列 \(q\) 与 \(q'\) 是等价的，如果属于 \(X_i\cup Y_i\) 的那些元素在两个排列中占据相同的位置集合。注意，我们并不要求每个元素 \(z\in X_i\cup Y_i\) 在 \(q\) 与 \(q'\) 中处于同一位置；我们要求的只是：属于 \(X_i\cup Y_i\) 的元素所占据的位置集合在 \(q\) 与 \(q'\) 中相同。

那么共有 \(\dbinom{n}{2k}\) 个等价类，每个等价类含 \(k!\cdot k!\,(n-2k)!\) 个排列。事实上，为属于 \(X_i\cup Y_i\) 的元素选取位置集合有 \(\dbinom{n}{2k}\) 种方式。一旦该集合选定，\(X_i\) 的 \(k\) 个元素必须排在该位置集合的前一半（顺序任意），\(Y_i\) 的 \(k\) 个元素必须排在后一半（顺序也任意）。最后，不属于 \(X_i\cup Y_i\) 的元素可以任意排列。这一论证对任意固定的 \(i\) 都成立，于是 \[\tag{6.7}P=m\cdot\binom{n}{2k}\cdot k!\cdot k!\,(n-2k)!=\frac{m\cdot n!}{\binom{2k}{k}}.\]

现在按排列 \(p\) 来数满足条件的对 \((p,i)\)。固定 \(p\)。我们断言：至多有一个下标 \(i\) 使 \((p,i)\) 满足条件。否则，假设 \(i\) 与 \(j\) 都是这样的下标。不失一般性，设 \(p\) 中 \(X_i\) 的最右元素弱地在 \(X_j\) 的最右元素的右侧。这将意味着 \(X_j\cap Y_i=\varnothing\)，矛盾。事实上，\(p\) 中 \(X_i\) 的所有元素都排在 \(Y_i\) 的所有元素之前，而由于 \(X_j\) 比 \(X_i\) 更早结束，\(X_j\) 的所有元素也都必须排在 \(Y_i\) 的所有元素之前，从而 \(X_j\) 与 \(Y_i\) 不相交。图 6.11 给出了图示。

X X X X X X X Y Y 蓝=Xᵢ 红=Xⱼ（Xⱼ 更早结束） Yᵢ 全在右侧
图 6.11　若 \(X_j\) 比 \(X_i\) 更早结束，则 \(X_j\) 整体落在 \(Y_i\) 的左边，于是 \(X_j\) 与 \(Y_i\) 不相交。

既然对每个排列 \(p\) 至多有一个下标 \(i\)，我们当然有 \(P\le n!\)。把这个不等式与 (6.7) 比较，得到 \(\dfrac{m\cdot n!}{\binom{2k}{k}}\le n!\)，即 \(m\le\dbinom{2k}{k}\)，正如所断言。♦

把定理 6.35 的两次计数串起来同一个量 \(P\)，从两个角度各数一遍，再夹逼：
  1. 按 \(i\) 数：每个 \(i\) 贡献 \(\dfrac{n!}{\binom{2k}{k}}\) 个合格排列，共 \(m\) 个 \(i\)，所以 \(P=\dfrac{m\,n!}{\binom{2k}{k}}\)。
  2. 按 \(p\) 数：每个排列至多配 \(1\) 个下标，所以 \(P\le n!\)。
  3. 两式相比即 \(\dfrac{m\,n!}{\binom{2k}{k}}\le n!\)，约去 \(n!\) 得 \(m\le\dbinom{2k}{k}\)，于是边数 \(|\mathcal{F}|=2m\)？——注意定理结论 \(|\mathcal{F}|\le\binom{2k}{k}\) 指的正是 \(m\) 的上界（这里 \(\mathcal{F}\) 由 \(m\) 对 \(X_i,Y_i\) 给出，约定按其表述计 \(m\le\binom{2k}{k}\)）。

请读者证明这个上界不能再被改进（补充习题 13）。然后请读者把本定理的结论推广到非一致的超图（补充习题 14）。

6.2.1.1　向日葵

在定理 6.34 与定理 6.30 所讨论情形中被证明为最优的那些构造里，我们看到了一些“边的交集非空”的超图的例子。这个概念可以被加强：要求任意两条边的交集不仅非空，而且始终相同。这一类超图如此重要，以至于它有自己的名字。

定义 6.36 一个由非空边组成的超图 \(\mathcal{H}\) 称为向日葵（sunflower），如果 \(\mathcal{H}\) 中每一对边都具有相同的交集；这个公共交集称为该向日葵的花心（core）。向日葵的各条边称为花瓣（petals）。
例 6.37 由边 \(\{1,k\}\)（其中 \(k\) 取遍集合 \(\{2,3,\dots,n\}\)）组成的超图是一个向日葵。图 6.12 给出了 \(n=9\) 时这个向日葵的图示，以及“向日葵”这个名字的由来。
1 2 3 4 5 6 7 8 9
图 6.12　\(n=9\) 的向日葵：花心 \(\{1\}\) 在正中（金色），\(8\) 条边 \(\{1,2\},\{1,3\},\dots,\{1,9\}\) 像花瓣一样从花心伸出，任意两片花瓣的公共部分都恰是花心 \(\{1\}\)。

注意，花心是允许为空的。还要注意，定义 6.36 等价于说：任意两条边的交集等于全部边的交集。

例如，若 \(\mathcal{F}\) 的各条边两两不相交，则 \(\mathcal{F}\) 是一个向日葵——尽管这并不是一个特别精彩的例子（此时花心为空）。更有趣的是：足够大的超图总会含有向日葵。这正是著名的 Erdős–Rado 引理（Erdős–Rado lemma）的内容。我们称 \(\mathcal{H}\) 是一个 \((p,\ell)\)-向日葵，如果 \(\mathcal{H}\) 是一个有 \(p\) 片花瓣、且每片花瓣都不超过 \(\ell\) 个顶点的向日葵。

把“向日葵”的定义钉死“每一对边交集都相同”这句话，等价于“两两交 = 全体交”。验证一下例 6.37：
  1. 任取两片花瓣，例如 \(\{1,3\}\) 与 \(\{1,7\}\)，它们的交是 \(\{1\}\)。
  2. 换一对，例如 \(\{1,2\}\) 与 \(\{1,9\}\)，交还是 \(\{1\}\)。
  3. 所有花瓣的总交集也是 \(\{1\}\)。两两交与全体交一致，故确为向日葵，花心 \(=\{1\}\)。
而“两两不相交”也是一种向日葵：任意两条边的交都是空集 \(\varnothing\)，全体交也是 \(\varnothing\)，故花心为空——只是这种向日葵没什么内容。

返回 全书目录