1. 概要

本記事では，ブール束 $B_n$ における反鎖の最大サイズを与える Sperner の定理を解説します．

Sperner の定理は，集合 $\lbrace 0,1,\dots,n-1\rbrace$ の部分集合を，どの $2$ つも互いに包含関係がないように選ぶときに，選べる部分集合の個数の最大値が

$$ \binom{n}{\lfloor n/2\rfloor} $$

であることを主張する定理です．本記事ではこの定理について $2$ 通りの証明を与え，等号成立条件やいくつかの関連事項についても解説します．これらの議論は，鎖や反鎖といった順序集合における重要概念に慣れるための題材としても適切です．

2. 前提知識

特にありません．

3. Sperner の定理

本記事において $n$ は非負整数を表すものとし，集合 $\lbrace 0,1,\dots,n-1\rbrace$ の部分集合全体をブール束（boolean lattice）と呼び，$B_n$ と書きます．

特に $B_n$ における部分集合関係 $\subseteq$ に注目します（学術語でいえば，$B_n$ の順序集合としての性質に注目します）．

3.1. Hasse 図

$B_n$ に対して，$S,T\in B_n$ が $S\subseteq T$ かつ $|T|=|S|+1$ を満たすときに限り $S\to T$ という有向辺を張ると，$B_n$ を頂点集合とする DAG が得られます．この DAG（またはそれを図示したもの）を $B_n$ の Hasse 図（Hasse diagram）といいます．

例えば $n=3, 4$ の場合の Hasse 図は次のようになります．

本記事では Hasse 図について，このように，同じ要素数の部分集合を同じ高さに並べるという図示を用います．

3.2. 鎖と反鎖

部分集合関係について，$2$ つの基本的な定義を述べます．

【定義 1】（鎖）
$B_n$ の部分集合 $\mathcal{C}=\lbrace S_0,S_1,\ldots,S_{m-1}\rbrace$ が鎖（chain）であるとは，任意の $i,j$ に対して $S_i\subseteq S_j$ または $S_j\subseteq S_i$ が成り立つことをいう．

【定義 2】（反鎖）
$B_n$ の部分集合 $\mathcal{A}=\lbrace S_0,S_1,\ldots,S_{m-1}\rbrace$ が反鎖（antichain）であるとは，任意の相異なる $i,j$ に対して $S_i\subseteq S_j$ でも $S_j\subseteq S_i$ でもないことをいう．

$n=3$ とするとき，例えば次が成り立ちます．

$\lbrace \emptyset,\lbrace 0\rbrace,\lbrace 0,1\rbrace,\lbrace 0,1,2\rbrace \rbrace$ は鎖である．反鎖ではない．
$\lbrace \lbrace 0\rbrace,\lbrace 0,1,2\rbrace\rbrace$ は鎖である．反鎖ではない．
$\lbrace \lbrace 1\rbrace,\lbrace 0,2\rbrace\rbrace$ は鎖ではない．反鎖である．
$\lbrace \lbrace 0,1\rbrace,\lbrace 0,2\rbrace,\lbrace 1,2\rbrace\rbrace$ は鎖ではない．反鎖である．
$\lbrace \lbrace 0,2\rbrace\rbrace$ は鎖である．反鎖である．
$\lbrace \lbrace 0\rbrace,\lbrace 1\rbrace,\lbrace 1,2\rbrace\rbrace$ は鎖ではない．反鎖ではない．

鎖と反鎖の関係としては，次の命題が基本的です．

【命題 3】
鎖 $\mathcal{C}$ および反鎖 $\mathcal{A}$ に対して $|\mathcal{C}\cap \mathcal{A}|\leq 1$．

相異なる集合 $S, T\in B_n$ が $\mathcal{C}$ と $\mathcal{A}$ の両方に含まれるとします．$\mathcal{C}$ が鎖であることから $S\subseteq T$ または $T\subseteq S$ となりますが，いずれにせよ $\mathcal{A}$ が反鎖であることに矛盾します．$\blacksquare$

3.3. 定理の主張

非負整数 $k$ （$0\leq k\leq n$）に対して，集合 $\lbrace 0,1,\dots,n-1\rbrace$ の部分集合であって，要素数が $k$ であるもの全体を $B_{n,k}$ と書くことにします．

$B_{n,k}$ が反鎖であることは容易に分かります．特に $k=\lfloor n/2\rfloor$ とすることで，$\displaystyle \binom{n}{\lfloor n/2\rfloor}$ 個の集合からなる反鎖が存在することが分かります．

Sperner の定理は，これが最大の反鎖であることを主張するものです．

【定理 4】（Sperner の定理）
任意の反鎖 $\mathcal{A}\subseteq B_n$ に対して $$ |\mathcal{A}|\leq \binom{n}{\lfloor n/2\rfloor} $$ が成り立つ．

本記事の目標は，Sperner の定理を証明することです．

4. 証明 1：LYM 不等式による証明

4.1. LYM 不等式

$p=(p_0,p_1,\ldots,p_{n-1})$ を順列とするとき，次のような，要素数 $0, 1, 2, \ldots, n$ の部分集合をひとつずつ含む鎖を考えることができます．

$$ \lbrace \emptyset,\quad \lbrace p_0\rbrace,\quad\lbrace p_0,p_1\rbrace,\quad\ldots,\quad \lbrace p_0,p_1,\ldots,p_{n-1}\rbrace \rbrace. $$

以下，この鎖を $\mathcal{C}_p$ と書くことにします．

【定理 5】（LYM 不等式（Lubell–Yamamoto–Meshalkin inequality））
反鎖 $\mathcal{A}\subseteq B_n$ に対して $$ \sum_{S\in\mathcal{A}}\binom{n}{|S|}^{-1}\leq 1 $$ が成り立つ．

順列 $p$ を，$n!$ 通り全体の中から一様ランダムに選ぶとき，$|\mathcal{C} _ p\cap \mathcal{A}|$ の期待値 $E$ について考えます．

まず【命題 3】より，任意の $p$ に対して $| \mathcal{C} _ p \cap \mathcal{A} | \leq 1$ です．したがって，$E\leq 1$ です．

次に，$S\in \mathcal{A}$ に対して，$S \in \mathcal{C} _ p$ が成り立つ確率を考えます．$m=|S|$ とすると，$\mathcal{C} _ p$ は $m$ 元集合を唯一含みます．$p$ を一様ランダムに選ぶとき，$\mathcal{C} _ p$ が含む唯一の $m$ 元集合としては，$\displaystyle \binom{n}{m}$ 個ある $m$ 元集合すべてが等確率で現れます．したがって，$S\in \mathcal{C} _ p$ となる確率は $\displaystyle \binom{n}{|S|}^{-1}$ です．

$|\mathcal{C} _ p \cap \mathcal{A}|$ の期待値 $E$ は，各 $S\in \mathcal{A}$ に対して $S\in \mathcal{C}_p$ となる確率の総和なので，

$$ E=\sum_{S\in\mathcal{A}}\binom{n}{|S|}^{-1} $$

です．以上を合わせて定理が示されました．$\blacksquare$

4.2. Sperner の定理の証明

二項係数 $\displaystyle \binom{n}{k}$ は $k=\lfloor n/2\rfloor$ のとき最大であることから，任意の部分集合 $S$ に対して

$$ \binom{n}{|S|}^{-1} \geq \binom{n}{\lfloor n/2\rfloor}^{-1} $$

が成り立ちます．これを LYM 不等式に代入すると

$$ 1 \geq \sum_{S \in \mathcal{A}} \binom{n}{|S|} ^ {-1} \geq \sum _ {S\in \mathcal{A}} \binom{n}{\lfloor n/2\rfloor} ^ {-1} = |\mathcal{A}| \cdot \binom{n}{\lfloor n/2\rfloor} ^ {-1} $$

が得られます．したがって

$$ |\mathcal{A}|\leq \binom{n}{\lfloor n/2\rfloor} $$

が示されました．$\blacksquare$

4.3. 等号成立条件

Sperner の定理において，最大値を達成する反鎖も完全に分類できます．

【定理 6】（Sperner の定理の等号成立条件）

反鎖 $\mathcal{A}\subseteq B_n$ が

$$ |\mathcal{A}|=\binom{n}{\lfloor n/2\rfloor} $$

を満たすとする．このとき，以下が成り立つ．

$n$ が偶数ならば，$\mathcal{A}=B_{n,n/2}$ である．
$n$ が奇数ならば，$\mathcal{A}=B_{n,(n-1)/2}$ または $\mathcal{A}=B_{n,(n+1)/2}$ である．

$\displaystyle |\mathcal{A}|=\binom{n}{\lfloor n/2\rfloor}$ であるとき，LYM 不等式および 4.2 節の証明における不等式評価において，すべて等号が成り立つことが必要です．つまり，以下が必要です．

条件 1：任意の順列 $p$ に対して $|\mathcal{C}_p\cap \mathcal{A}|=1$．
条件 2：任意の $S\in \mathcal{A}$ に対して $\displaystyle \binom{n}{|S|}=\binom{n}{\lfloor n/2\rfloor}$．

まず $n$ が偶数であるとします．すると条件 2 から，任意の $S\in \mathcal{A}$ に対して $|S|=\lfloor n/2\rfloor$ が成り立ちます．このことと $\displaystyle |\mathcal{A}|=\binom{n}{\lfloor n/2\rfloor}$ から $\mathcal{A}=B_{n,n/2}$ が成り立ちます．

以下，$n=2m+1$ が奇数であるとします．条件 2 から，任意の $S\in \mathcal{A}$ に対して $|S|$ は $m$ または $m+1$ です．

$\mathcal{A} = B _ {n, m+1}$ ではないことを仮定して，$\mathcal{A}=B_{n,m}$ であることを示します．そのためには $\mathcal{A}$ が $m$ 元集合を含むことを仮定して，すべての $m$ 元集合を含むことを示せばよいです．そのためには，次を示せばよいです：

$S$ を反鎖 $\mathcal{A}$ に含まれる $m$ 元集合とし，$x\in S, y\notin S$ とするとき，$T=S\setminus \lbrace x\rbrace \cup \lbrace y\rbrace$ も $\mathcal{A}$ に含まれる．

$S\cup\lbrace y\rbrace=T\cup \lbrace x\rbrace$ なので，ある順列 $p$ が存在して，$\mathcal{C} _ p$ は $T$ と $S \cup \lbrace y\rbrace$ をどちらも含みます．条件 1 から $\mathcal{C}_p$ は $\mathcal{A}$ と交わりますが，$\mathcal{A}$ の要素は $m$ 元集合と $m+1$ 元集合のどちらかなので，$T$ と $S\cup\lbrace y\rbrace$ のどちらかが $\mathcal{A}$ に含まれなければなりません．

一方，$S\in \mathcal{A}$ と $\mathcal{A}$ が反鎖であることから $S\cup\lbrace y\rbrace \notin \mathcal{A}$ です．したがって $T\in \mathcal{A}$ が得られます．

ここで示された

$$ S\in \mathcal{A}\implies T=S\setminus \lbrace x\rbrace \cup \lbrace y\rbrace \in \mathcal{A} $$

を繰り返し用いることで，$\mathcal{A}$ が $m$ 元集合を含むならばすべての $m$ 元集合を含むことが分かります．$|\mathcal{A}| = |B _ {n,m}|$ なので $\mathcal{A} = B _ {n,m}$ となります．以上により $n$ が奇数の場合も示されました．$\blacksquare$

5. 証明 2：対称鎖分解による証明

5.1. 対称鎖

【定義 7】（対称鎖）

$\lbrace 0,1,\ldots,n-1\rbrace$ の部分集合 $S_0,S_1,\ldots,S_m$ （$m\geq 0$）について，

$S_0\subsetneq S_1\subsetneq \cdots \subsetneq S_m$．
$|S_{i+1}|=|S_i|+1$ $(0\leq i < m)$．
$|S_0|+|S_m|=n$．

が成り立つとき，鎖 $\mathcal{C}=\lbrace S_0,S_1,\ldots,S_m\rbrace$ を $B_n$ の対称鎖（symmetric chain）という．

例えば $n=3$ のとき，

$\lbrace \emptyset,\lbrace 0\rbrace,\lbrace 0,1\rbrace, \lbrace 0,1,2\rbrace \rbrace$ は対称鎖です．
$\lbrace \lbrace 0\rbrace,\lbrace 0,1\rbrace \rbrace$ は対称鎖です．
$\lbrace \emptyset,\lbrace 0,1,2\rbrace \rbrace$ は対称鎖ではありません．
$\lbrace \lbrace 0\rbrace, \lbrace 0,1\rbrace, \lbrace 0,1,2\rbrace \rbrace$ は対称鎖ではありません．

5.2. 対称鎖分解

【定理 8】
$B_n$ は，互いに交わらない対称鎖の和集合として表すことができる．

$n$ に関する帰納法により示します．$n=0$ の場合は明らかです．$n$ を正整数とし，$n-1$ の場合を仮定して $n$ の場合を示します．

$S\in B _ {n-1}$ に対して，$S\cup\lbrace n-1\rbrace \in B _ {n}$ を $S ^ +$ と書くことにします．

$B _ {n-1}$ が対称鎖に分解されているとします．これらの各対称鎖を

$$ S_0\subsetneq S_1\subsetneq \cdots \subsetneq S_m $$

としたとき，この対称鎖を次のように，$B_n$ の $2$ つの対称鎖に置き換えます．

$S_0\subsetneq S_1\subsetneq \cdots \subsetneq S_{m-1}\subsetneq S_m\subsetneq S_m^+$．
$S_0^+\subsetneq S_1^+\subsetneq \cdots \subsetneq S_{m-1}^{+}$．

ただし，$m=0$ の場合については前者の対称鎖 $1$ つだけに置き換えます．これらが対称鎖になることについては，

$|S_0|+|S_{m} ^ +|=|S_0|+(|S_m|+1)=n$
$|S_0 ^ +|+|S _ {m-1} ^ +|=(|S _ 0|+1)+(|S _ {m-1}|+1)=|S_0|+|S_m|+1=n$

であることから分かります．

$B_n$ の要素はすべて $B _ {n-1}$ の要素 $S$ を用いて，$S$ または $S ^ +$ の形で一意に表せるので，すべての $B_{n-1}$ の対称鎖について上述の置き換えをすれば，$B_n$ の対称鎖分解が得られます．$\blacksquare$

上の証明の方法による $B_n$ の対称鎖分解を図示すると，次のようになります．

5.3. Sperner の定理の証明

$k=\lfloor n/2\rfloor$ とします．

対称鎖 $\mathcal{C}$ に含まれる集合の要素数の最小値を $a$，最大値を $b$ とすると，$a\leq b$ かつ $a+b=n$ より $a\leq k\leq b$ が成り立ちます．したがってすべての対称鎖は，$k$ 元集合をちょうど $1$ つ含むので，対称鎖分解はちょうど $\displaystyle \binom{n}{k}$ 個の対称鎖からなります．

このことと【命題 3】より，任意の反鎖の大きさは $\displaystyle \binom{n}{k}$ 以下です．$\blacksquare$

5.4. 関連：$\boldsymbol{B _ {n,k}}$ と $\boldsymbol{B _ {n,k+1}}$ のマッチング

対称鎖分解から，$B _ {n,k}$ と $B _ {n,k+1}$ の包含関係に関する最大マッチングが得られます．

【系 9】

$k$ を $0\leq k < n$ を満たす非負整数とする．このとき，$S_0, S_1, \ldots, S_{m-1} \in B_{n,k}$ および $T_0, T_1, \ldots, T_{m-1}\in B_{n,k+1}$ であって以下を満たすものが存在する．

$i\neq j$ ならば $S_i\neq S_j$，$T_i\neq T_j$．
任意の $i$ に対して $S_i\subsetneq T_i$．
$\displaystyle m = \min\left(\binom{n}{k},\binom{n}{k+1}\right)$，つまり $k< \lfloor n/2\rfloor$ ならば $\displaystyle m=\binom{n}{k}$，$\lfloor n/2\rfloor \leq k$ ならば $\displaystyle m=\binom{n}{k+1}$．

$B_n$ の対称鎖分解を考えます．要素数 $k$ の集合と要素数 $k+1$ の集合の両方を含む対称鎖を $\mathcal{C} _ 0, \mathcal{C} _ 1, \ldots, \mathcal{C} _ {m-1}$ として，$\mathcal{C}_i$ が含む要素数 $k$ の集合を $S_i$，要素数 $k+1$ の集合を $T_i$ とします．

対称鎖という条件から，$k<\lfloor n/2\rfloor$ ならば，要素数 $k$ の集合を含む対称鎖は必ず要素数 $k+1$ の集合も含みます．したがって，$\displaystyle m=\binom{n}{k}$ が成り立ちます．$\lfloor n/2\rfloor\leq k$ の場合も同様に $\displaystyle m=\binom{n}{k+1}$ が分かります．

これらが条件を満たすことは容易に確かめられます．$\blacksquare$

なお，本記事の解説順とは逆に，【系 9】を証明することで Sperner の定理を証明するという方向の議論も可能です．マッチング関係にある組 $(S_i,T_i)$ が同じ鎖に含まれるようにすれば，$B_n$ を $\displaystyle \binom{n}{\lfloor n/2\rfloor}$ 個の鎖に分解できるからです．

5.5. 関連：鎖の直積の場合

Sperner の定理は，ブール束 $B_n$ に限らず，鎖の直積と呼ばれるタイプの順序集合にも一般化されます．ここでは簡潔に定義と結論だけ述べておきます．

$a_0,a_1,\ldots,a_{n-1}$ を正整数とし，集合 $B$ を

$$ B = \lbrace (s_0,s_1,\ldots,s_{n-1})\mid s_i \in \mathbb{Z}, 0\leq s_i\leq a_i\rbrace $$

とします．さらに次の定義をします．

$S = (s_0,s_1,\ldots,s _ {n-1}), T = (t_0,t_1,\ldots,t _ {n-1})\in B$ に対して，任意の $i$ に対して $s_i\leq t_i$ が成り立つとき，$S\leq T$ であると定義する．
$B$ の部分集合 $\mathcal{A}=\lbrace S_0,S_1,\ldots,S_{m-1}\rbrace$ が反鎖（antichain）であるとは，任意の相異なる $i,j$ に対して $S_i\leq S_j$ でも $S_j\leq S_i$ でもないことをいう．

【定理 10】

$k = \left\lfloor\dfrac{a_0+a_1+\cdots+a_{n-1}}{2}\right\rfloor$ とするとき，

$$ \lbrace (s_0,s_1,\ldots,s_{n-1})\in B\mid s_0+s_1+\cdots+s_{n-1}=k\rbrace$$

は要素数が最大の反鎖のひとつである．

対称鎖分解を用いる Sperner の定理の証明が，比較的そのままに近い形でこの定理の証明に一般化可能です．ここでは詳細を省略しますが，帰納法の各ステップを表す図だけ載せておくので，興味があれば証明を考えてみてください．

6. 関連問題

問題について

1, 2 は $k$ 元部分集合と $k+1$ 元部分集合のマッチングに関する構築問題で，本記事で解説した存在証明をそのままアルゴリズムとして実装することで解くことができます．他にも様々な解法があるので，興味があれば提出例などから確認してみてください．

3 は鎖の直積の最大反鎖に関する問題です．4 は問われていることをよく整理すると，$B_n$ の最大反鎖に関する問題として見ることができます．

7. まとめ

本記事では，ブール束 $B_n$ の最大反鎖に関する Sperner の定理について，2 通りの証明を解説しました．ひとつは LYM 不等式を経由する証明，もうひとつは鎖分解を用いる証明です．いずれの証明もブール束に限らず，より広い順序集合に一般化される重要な考え方です．

鎖や反鎖は，順序集合における基礎概念で，他にも Mirsky の定理や Dilworth の定理などの結果が競技プログラミングでは重要です．特に，鎖分解やマッチングを用いる Sperner の定理の証明は，Dilworth の定理と類似の考え方に基づくものと見ることができます．Sperner の定理は，このような順序集合論の基本的な考え方を，ブール束という具体的で扱いやすい対象を通して理解できる代表的な例といえるでしょう．

8. 参考文献

Emanuel Sperner．Ein Satz über Untermengen einer endlichen Menge．Mathematische Zeitschrift．Vol. 27．No. 1．pp. 544–548．1928．DOI: 10.1007/BF01171114．https://doi.org/10.1007/BF01171114．
Wikipedia．Sperner's theorem．https://en.wikipedia.org/wiki/Sperner%27s_theorem．（閲覧日: 2026-04-25）．
Wikipedia．Lubell–Yamamoto–Meshalkin inequality．https://en.wikipedia.org/wiki/Lubell%E2%80%93Yamamoto%E2%80%93Meshalkin_inequality．（閲覧日: 2026-04-25）．
Wikipedia．Dilworth's theorem．https://en.wikipedia.org/wiki/Dilworth%27s_theorem．（閲覧日: 2026-04-25）．
noshi91．2 要素の分離を網羅するテクニック．https://noshi91.hatenablog.com/entry/2024/05/31/012055．（閲覧日: 2026-04-25）．

トップページ：AtCoder Algorithm Lectures