スペルナーの定理

この定理の証明は簡単である。

に含まれる集合の部分集合はすべてに含まれることから、

• に含まれるサイズiの要素1つに対して、その部分集合としてi個、サイズi−1の要素が存在 している。
  (i個の要素から1つ取り除く方法はi通りあるため。)

• 逆に、サイズi−1の要素の方から見ると、その要素を含むサイズiの要素の個数は高々m−i＋1個である。
  (i−1個の要素に1つ付け加える方法はm−i＋1通りあるため。)

ここで、包含関係のあるようなサイズiの集合とサイズi−1の集合の組の個数をxとすると、

• 1つ目の観察から x＝i・F_i、
• 2つ目の観察から x≦(m−i＋1)F_i-1

i・F_i≦(m−i＋1)F_i-1

すなわち、F_i-1 ≧ (i／(m−i＋i))・F_iという不等式が得られることになる。
(証明終り)

注： このように、ある性質を満たす集合族(この場合は単体的複体である、つまり、部分集合に閉じている集合族)に対して、限界ぎりぎりの状況ではどのようなことが起こっているか？(この場合は、F_i-1をどこまで下げられるか？)というような議論は、「極値集合論」(extremal set theory)と呼ばれる分野で行なわれている。離散数学・組合せ論の重要な分野の一つである。