極値集合論とは何らかの条件を満たす有限集合の族うち、最も大きいものあるいは最も小さいものを探求する研究分野である。もっとも有名な定理はエルデシュ・コ・ラドの定理で、カトーナの円形置換法など、エレガントな証明がいろいろ知られているという。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】エルデシュ・コ・ラドの定理

ｎ点集合Ｘのｋ点部分集合A1,A2,・・・,Amを考える。もし、ｋ＜ｎ/2ならば、すべてのi、jに対して、Ai∩Aj≠0となるものが何個とれるか？

ｍ≦(n-1,k-1)

もし相互に交わるｋ点部分集合が共通な１点をもななければmosi

ｍ≦(n-1,k-1)-(n-k-1,k-1)+1

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】クラスカル・カトーナの定理

{1,2,・・・,n}のk点部分集合をすべて書き出すためのいい方法はあるか？

{1,2,3,4,5}の３点部分集合を

[1]辞書式順序で書き出すと

{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5}

{1,4,5},{2,3,4},{2,3,5},{2,4,5},{3,4,5}

[2]長さ5の2進法表記の辞書式順序（圧縮順序）

{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,5}=00111,01011,01101,01110,10011

{1,3,5},{2,3,5},{1,4,5},{2,4,5},{3,4,5}=10101,10110,11001,11010,11100

4つの３点部分集合が与えられたとすると、大きさが２の部分集合がどれだけ含まれているのだろうか？

[1]辞書式順序の場合、

たとえば、{1,2,4},{2,3,5},{1,3,4},{2,3,4}が与えられたと仮定する。

{1,2},{1,3},{1,4},{2,3},{2,4},{2,5},{3,4},{3,5}の8個を含む

[2]長さ5の2進法表記の辞書式順序（圧縮順序）

{1,2,3},{1,2,4},{1,3,4},{2,3,4}が与えられたと仮定する。

{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}の6個を含む

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

{1,2,・・・,n}のr個のk点部分集が、それに含まれる(k-1)点部分集合の数を最小化するためには圧縮集合の最初のr個を選べばよい

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝