Kruskal–Katona 定理

克鲁斯卡尔–卡托纳定理
术语名称	克鲁斯卡尔–卡托纳定理
英语名称	Kruskal–Katona theorem

Kruskal–Katona 定理(Kruskal–Katona theorem)描述了集合族大小与其“阴影”大小之间的关系。

定义

均匀族

对集族，若集族内每个集合的大小都为 [math]\displaystyle{ k }[/math] ，称为一个 [math]\displaystyle{ k }[/math]-均匀族([math]\displaystyle{ k }[/math]-uniform family)，

阴影

设 [math]\displaystyle{ \mathcal{F} }[/math] 是一个 [math]\displaystyle{ k }[/math]-均匀族，定义其中： [math]\displaystyle{ \partial_l \mathcal{F} = \{G \mid \operatorname{card}G = l \exists F \in \mathcal{F} (G \subset F)\}$$ 称为其 \lt math\gt l }[/math]-阴影([math]\displaystyle{ l }[/math]-shadow)。

[math]\displaystyle{ (k-1) }[/math]-阴影可以简称阴影，记作 [math]\displaystyle{ \partial \mathcal{F} }[/math] 。

二项表示

任意正整数 [math]\displaystyle{ m }[/math] 和 [math]\displaystyle{ k }[/math] ， [math]\displaystyle{ m }[/math] 可以唯一表示为： [math]\displaystyle{ m = \binom{a_k}{k} + \binom{a_{k-1}}{k-1} + \cdots + \binom{a_t}{t} }[/math] 其中 [math]\displaystyle{ a_k \gt a_{k-1} \gt \cdots \gt a_t \geq t \geq 1 }[/math] ，都是由 [math]\displaystyle{ m, k }[/math] 决定的参数。

定理

对任意 [math]\displaystyle{ k }[/math]-均匀族 [math]\displaystyle{ \mathcal{F} }[/math] ，其 [math]\displaystyle{ l }[/math]-阴影的大小满足： [math]\displaystyle{ |\partial_l \mathcal{F}| \geq \binom{a_k}{l} + \binom{a_{k-1}}{l-1} + \cdots + \binom{a_t}{l-k+t} }[/math] 。 其中 [math]\displaystyle{ a_i, t\leq i\leq k }[/math] 是 [math]\displaystyle{ m }[/math] 的 [math]\displaystyle{ k }[/math]-二项表示中的参数。

特别地， [math]\displaystyle{ |\partial \mathcal{F}| = \binom{a_k}{k-1} + \binom{a_{k-1}}{k-2} + \cdots + \binom{a_t}{t-1} }[/math] 。 取等号当且仅当 $\mathcal{F}$ 由尾字典序下前 $|\mathcal{F}|$ 个 $k$-子集组成。