查看“︁Kruskal–Katona 定理”︁的源代码

[[分类:极值集合论]]
[[分类:以 Kruskal 命名]]
[[分类:以 Katona 命名]]{{DEFAULTSORT:kruskal katona ding4li3}}
{{#seo:
|keywords=Kruskal–Katona 定理, 克鲁斯卡尔–卡托纳定理
|description=本文介绍Kruskal–Katona定理的内容，包括相交k-均匀族的l-阴影大小的关系。
|modified_time={{REVISIONYEAR}}-{{REVISIONMONTH}}-{{REVISIONDAY2}}
|published_time=2025-10-26
}}
{{InfoBox
|name=克鲁斯卡尔–卡托纳定理
|eng_name=Kruskal–Katona theorem
}}
'''Kruskal–Katona 定理'''('''Kruskal–Katona theorem''')描述了集合族大小与其“阴影”大小之间的关系。

== 定义 ==

=== 均匀族 ===

对集族，若集族内每个集合的大小都为 <math>k</math> ，称为一个 '''<math>k</math>-均匀族'''('''<math>k</math>-uniform family''')，

=== 阴影 ===

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

<math>(k-1)</math>-阴影可以简称'''阴影'''，记作 <math>\partial \mathcal{F}</math> 。

=== 二项表示 ===

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

== 定理 ==

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

特别地， <math>|\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$-子集组成。