スペルナー家

組合せ論において、スペルナー族（スペルナーシステム、エマヌエル・スペルナーにちなんで名付けられた）またはクラッターは、有限集合Eの部分集合の族Fであり、その中のどの集合も他の集合を含まない。同様に、スペルナー族はEの冪集合上の包含格子の反鎖である。スペルナー族は独立系または非冗長集合と呼ばれることもある。

スペルナー族はデデキント数で数えられ、その大きさはスペルナーの定理とルベル・山本・メシャルキンの不等式によって制限される。また、集合族ではなくハイパーグラフの言語で記述されることがあり、その場合はクラッターと呼ばれる。

n個の元からなる集合上の異なるスペルナー族の数はデデキント数によって数えられ、そのうち最初のいくつかは

2、3、6、20、168、7581、7828354、2414682040998、56130437228687557907788（OEISの配列A000372）。

nの値が大きくなると正確な漸近推定値が得られることが分かっていますが、これらの数値を効率的に計算するために使用できる正確な公式が存在するかどうかは不明です。

n個の要素からなる集合上のすべてのスペルナー族の集合は、自由分配格子として構成できます。自由分配格子では、2 つのスペルナー族の結合は、2 つの族の和集合から、和集合内の別の集合のスーパーセットである集合を削除することによって得られます。

n元集合の k 元部分集合はスペルナー族を形成し、その大きさはk = n /2 (またはそれに最も近い整数) のときに最大になる。 スペルナーの定理は、これらの族がn元集合上の最大のスペルナー族であることを述べている。正式には、定理はn元集合上のすべてのスペルナー族Sについて、

${\displaystyle |S|\leq {\binom {n}{\lfloor n/2\rfloor }}.}$

ルベル・ヤマモト・メシャルキン不等式は、_{スペルナー}族の大きさに関する別の上限を与え、スペルナーの定理を証明するために使用できる。これは、n個 の要素からなる集合上のスペルナー族におけるサイズkの集合の数をkとすると、

${\displaystyle \sum _{k=0}^{n}{\frac {a_{k}}{n \choose k}}\leq 1.}$

クラッターとは、他のものを含まない有限集合の部分集合の族、つまりスペルナー族です。違いは、通常尋ねられる質問にあります。クラッターは、組み合わせ最適化の研究において重要な構造です。

より複雑な言葉で言えば、クラッタは、かつ（つまり、どの辺も他の辺を適切に含まない）という追加のプロパティを備えたハイパーグラフ です。 クラッタの反対の概念は、抽象的な単体複合体であり、ここでは、辺のすべての部分集合がハイパーグラフに含まれます。これは、 Vの部分集合の順序イデアルです。 ${\displaystyle (V,E)}$${\displaystyle A\not \subseteq B}$${\displaystyle A,B\in E}$${\displaystyle A\neq B}$

がクラッタである場合、 で表されるHのブロッキングは、頂点集合Vと、任意の に対して となるすべての極小集合からなる辺集合を持つクラッタです。 (Edmonds & Fulkerson 1970) であることが示されており、したがって、ブロッキングは一種の双対性を与えます。 をH内の最大の非結合辺集合のサイズ、を 内の最小の辺のサイズと定義します。 であることは簡単にわかります。 ${\displaystyle H=(V,E)}$${\displaystyle b(H)}$${\displaystyle B\subseteq V}$${\displaystyle B\cap A\neq \varnothing }$${\displaystyle A\in E}$${\displaystyle b(b(H))=H}$${\displaystyle \nu (H)}$${\displaystyle \tau (H)}$${\displaystyle b(H)}$${\displaystyle \nu (H)\leq \tau (H)}$

1. G が単純なループのないグラフである場合、 はクラッターであり (辺が順序付けられていない頂点のペアとして扱われる場合)、 はすべての最小頂点カバーのコレクションです。ここで、は最大マッチングのサイズであり、は最小の頂点カバーのサイズです。ケーニッヒの定理によれば、二部グラフの場合、 となります。ただし、他のグラフでは、これら 2 つの量は異なる場合があります。${\displaystyle H=(V(G),E(G))}$${\displaystyle b(H)}$${\displaystyle \nu (H)}$${\displaystyle \tau (H)}$${\displaystyle \nu (H)=\tau (H)}$
2. Gをグラフ、 とします。s - tパスのすべてのエッジ セットのコレクションHはクラッターであり、 はsとt を分離するすべての最小エッジ カットのコレクションです。この場合、はエッジが互いに素なs - tパスの最大数であり、 はsとt を分離する最小のエッジ カットのサイズであるため、メンガーの定理(エッジ接続バージョン) は であると主張します。${\displaystyle s,t\in V(G)}$${\displaystyle b(H)}$${\displaystyle \nu (H)}$${\displaystyle \tau (H)}$${\displaystyle \nu (H)=\tau (H)}$
3. G を連結グラフとし、 H を G の全域木のすべての辺集合からなる 上のクラッターとします。すると、はGのすべての極小辺カットセットの集合となります。${\displaystyle E(G)}$${\displaystyle b(H)}$

クラッターにも、グラフのマイナー関係に似たマイナー関係があります。 がクラッターで の場合、 v を削除して、 v を含まないすべての頂点セットと辺セットで構成されるクラッターを取得できます。v を縮約すると、クラッターが得られます。これら 2 つの操作は可換であり、Jが別のクラッターである場合、一連の削除と縮約によってHからJと同型のクラッターを取得できる場合、 J はHのマイナーであると言います。 ${\displaystyle H=(V,E)}$${\displaystyle v\in V}$ ${\displaystyle H\setminus v}$${\displaystyle V\setminus \{v\}}$${\displaystyle A\in E}$ ${\displaystyle H/v=b(b(H)\setminus v)}$

• アンダーソン、イアン（1987）「スペルナーの定理」、有限集合の組合せ論、オックスフォード大学出版局、pp. 2-4。
• エドモンズ、J.;フルカーソン、DR (1970)、「ボトルネック極値」、組み合わせ理論ジャーナル、8 (3): 299–306、doi : 10.1016/S0021-9800(70)80083-7。
• Knuth, Donald E. (2005)、「セクション 7.2.1.6: すべてのツリーの生成の草稿」、The Art of Computer Programming、第 4 巻、pp. 17–19。
• Sperner、Emanuel (1928)、「Ein Satz über Untermengen einer endlichen Menge」(PDF)、Mathematische Zeitschrift (ドイツ語)、27 (1): 544–548、doi :10.1007/BF01171114、JFM  54.0090.06。