群ラベル制約付き最短路問題

この記事は「データ構造とアルゴリズム Advent Calendar 2019」 4 日目の記事です.*1
3 日目は @921603 さんによる「Proximity search:列挙アルゴリズムの新たな構築手法」です.
5 日目は @TsuMakoto さんによる「IDA* with Pattern Databaseでパズルを解く」です.

グラフにおける最短路問題は組合せ最適化の古典的な問題ですよね.今回は,その制約付きの変種に対する効率的なアルゴリズムを紹介したいと思います.元ネタは,来年 1 月に開催される SODA という離散アルゴリズムの国際会議に採択されている以下の論文です.

Yutaro Yamaguchi: A Strongly Polynomial Algorithm for Finding a Shortest Non-zero Path in Group-Labeled Graphs. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), to appear.  (arXiv:1906.04062)

奇しくも著者の方とイニシャルが同じ (Y.Y.) でした.運命的ですね.

昨日は STOC だったし,最新の SODA と言うと「難しいんじゃ…?」と思う方も居るかもしれませんが,

- It gives a very simple algorithm for an important problem, ...

- The algorithm is simple enough to teach to undergraduates (without the proof of correctness, at least).

- The idea of the algorithm is simple to explain, ...

などと評価されていたため,きっと大丈夫かと思います.*2  これなら競技プログラミングの問題としても出題できそうですね!

では早速中身に入っていきましょう.以下では,入力グラフの頂点数を n,枝数を m で表すことにします.また,パスと言ったときには,単純経路を指すものとし,同じ頂点を複数回通るようなものは許さないことに注意してください.


無向グラフにおける最短路問題(制約無し)

古典的な問題とはいえ,導入として普通の最短路問題から始めましょう.

入力   G = (V, E): 無向グラフ,\ell \colon E \to \mathbf{R}_{\ge 0}: 枝長,s, t \in V: 端点対
目標   \ell に関して最短である G 中の st パス P の発見

f:id:ygussany:20191202184940p:plain
f:id:ygussany:20191202185102p:plain
図1: 最短路問題のインスタンスと最適解の例

この問題は,Dijkstra*3などを用いれば,効率的に*4解くことができます.

定理  (Dijkstra 1959)   最短路問題に対する決定性 \mathrm{O}(n^2) 時間アルゴリズムが存在する.*5

このアルゴリズムは,始点 s から到達可能な任意の点への \ell に関する最短路を含むような,G 中の木を計算できます.この木を,s を根とする (G, \ell) の最短路木と呼ぶことにします.


無向グラフにおける最短奇パス問題

効率的に解ける制約付き最短路問題として,以下の問題が知られています.

入力   G = (V, E): 無向グラフ,\ell \colon E \to \mathbf{R}_{\ge 0}: 枝長,s, t \in V: 端点対
目標   \ell に関して最短である G 中の奇数枝数 st パス P の発見

f:id:ygussany:20191202191038p:plain
f:id:ygussany:20191202191046p:plain
図2: 最短奇パス問題での実行不能P' と最適解 P の例

先ほどとの違いは,見つけたい対象に「奇数本の枝を使っている」という制約条件が加わったことだけです.*6  この問題は,最小重み完全マッチング問題に帰着でき,効率的に解けることが知られています.さらに,直接的で高速なアルゴリズムが設計できることも知られています.

定理  (Derigs 1985)*7   最短奇パス問題に対する決定性 \mathrm{O}(\min\{n^2, m\log n\}) 時間アルゴリズムが存在する.

今回紹介するアルゴリズムは,この Derigs のアルゴリズムに触発され,それを拡張したような形になっています.


群ラベル付きグラフにおける最短非零パス問題

さて,では今回扱う問題を導入しましょう.群ラベル付きグラフとは,無向グラフの各枝に,固定された群の要素がラベルとして付いているようなものです.ラベル付けには向きの情報が付随していて,逆向きに通ると逆元がラベルとして読まれるものとします.

抽象的な定義より,例を見た方が早いので,さっさと進みましょう.定義では \Gamma を任意の群としますが,馴染みが無ければ整数の加法群 (\mathbf{Z}, +) などを考えてもらえばよいです.実際,以下では \Gamma = (\mathbf{Z}, +) の場合を例に進めます.

入力   G = (V, E): \Gamma ラベル付きグラフ,\ell \colon E \to \mathbf{R}_{\ge 0}: 枝長,s, t \in V: 端点対
目標   \ell に関して最短である G 中の非零ラベル st パス P の発見

f:id:ygussany:20191202213440p:plain

図3: 最短非零パス問題のインスタンスの例(黒がラベル,青が枝長)
f:id:ygussany:20191202211741p:plain
f:id:ygussany:20191202211744p:plain
図4: 最短非零パス問題での実行不能P' と最適解 P の例

例を見てもらえればイメージは掴めると思いますが,この問題での目標は,パスに沿って自然に定まるラベル \psi_G(P) が非零である(群 \Gamma単位元でない)ような st パス P の中で,\ell に関して最短のものを求めることです.

この問題は,ラベル付けに用いる群 \Gamma に依って様子が変わってきます.たとえば,位数 2 の群 \mathbf{Z} / 2\mathbf{Z} = (\{0, 1\}, \oplus)\Gamma として選ぶと,先ほどの最短奇パス問題と本質的に等価な問題になります.また,曲面 S に埋め込まれたグラフに対し,S の基本群を \Gamma として選び,適切に枝のラベルを設定することで,埋め込まれた曲面上で非可縮な閉路*8を求める問題などを定式化することもできます.

今回紹介するのは,群 \Gamma に依らず*9,最短非零パス問題を効率的に解くアルゴリズムです.

定理  (Yamaguchi 2020)   最短非零パス問題に対する決定性 \mathrm{O}(nm) 時間アルゴリズムが存在する.


アルゴリズム

いよいよ本題のアルゴリズムの紹介です.方針は十分にシンプルで,以下の通りです.ここでも,簡単のため,\Gamma = (\mathbf{Z}, +) として話を進めますが,任意の群に取り替えても(非可換だろうが無限だろうが)正しく動くというのが紹介論文の強みです.

  1.  まず,制約を無視して Dijkstra 法で s を根とする (G, \ell) の最短路木 T を求める.
  2.  T に含まれる唯一の st パス P_t のラベルが非零 (\psi_G(P_t) \neq 0) であれば,P_t を出力して終了する.
  3.  \psi_G(P_t) = 0 であれば,P_t とラベルが違う st パスの中で \ell に関して最短のもの Q を求めて出力する.

f:id:ygussany:20191203085134p:plain

図5: 最短路木 T とステップ 3 での目標(Q の発見)

1, 2 は Dijkstra 法を実行して,その出力をチェックするだけなので,簡単にできますね.問題は 3 で,この部分を正しく実行するアルゴリズムが以下の主題となります.ここで,以下の補題が重要となります.直観的には,良い非零ラベル閉路 C が存在して,C が欲しい解を即座に誘導するか,そうでなければ C をある程度潰しても大丈夫である,ということを主張しています.

補題   任意の最短路木 T に対して,ある枝 e \in E \setminus T が存在して,T + e 中の唯一の閉路 C が以下の性質をすべて満たす.ここで,C 上で s に最も近い点を b とする.

  • C は非零ラベルである.(\psi_G(C) \neq 0)
  • C - b の任意の点 w に関して,C に関して T迂回して得られる sw パス Q_w は,\psi_G(Q_w) \neq \psi_G(P_w) を満たす中で \ell に関して最短の sw パスである.
  • C - b 以外の任意の点に関して,Cb適切に縮約すれば,問題(ステップ 3 での目標)を本質的に保ったままインスタンスのサイズを小さくできる.

f:id:ygussany:20191203090836p:plain

図6: 補題の気持ち

この補題により,現状のインスタンス(+最短路木)に関して条件を満たす枝 e を効率的に発見できさえすれば,

  • C - b 中に t が居れば,C に関する迂回路(を元のグラフに展開したもの)を出力,
  • C - b 外に t が居れば,Cb に適切に縮約して再帰

という単純な構造のアルゴリズムを作ることができます.各再帰では頂点数が必ず減るので,再帰の深さは高々 n で,一度でも前者の状況になれば終わりなので,繰り返し回数自体が n で押さえられますね.

「適切に縮約する」とは何なのか,ということを厳密に定義するのは,概念の簡単さに比べて不必要に面倒なので,直観的な説明と図だけに留めます.直観的には,b から C の周辺の各頂点への C に沿った部分パスの情報(ラベルと長さ)だけを,2 本の多重枝として残し,その他はすべて忘れてしまう,ということです.言い換えると,C と変な交わり方をするような st パスは,今回の問題を解く上では考える必要が無いということです.図は気持ちで読み取ってください.

f:id:ygussany:20191203093906p:plain

図7: 適切な縮約(C に沿った部分パスの情報だけを残す)

さて,最後に,補題の条件を満たす枝 e を効率的に見つけられるかという問題を解決しましょう.これには簡単な判定方法があり,毎回 \mathrm{O}(m) 時間で見つけられる,ということが以下の主張から従います.再帰の回数が高々 n であったので,これにより,全体として \mathrm{O}(nm) 時間のアルゴリズムが完成します.

主張   任意の最短路木 T に対して,非零ラベル閉路 C を形成するような枝 e = \{u, v\} \in E \setminus T のうち,\frac{1}{2}\left(\ell(P_u) + \ell(P_v) + \ell(e)\right) を最小にするようなものを選べば,補題の条件を満たす.

論文中では,T + e に含まれるような非零ラベル閉路 C を blossom と呼び,主張中で定義されている値をその高さと定義し,最も低い blossom を探せば良い,と書かれています.

f:id:ygussany:20191203092507p:plain

図8: 主張の気持ち(最も低い blossom を見つければよい)


まとめ

群ラベル付きグラフにおける最短非零パス問題に対して,ラベル付けに用いる群に依らない多項式時間アルゴリズムを紹介しました.アイデアとしては,

  • まず Dijkstra 法で最短路木 T を求めて,
  • T 中の st パス P_t が非零ラベルならそれを出力して終わりで,
  • そうでなければ,
    • T に関する良い非零ラベル閉路 C (with b) を(最も低い blossom を)見つけて,
    • C - b 上に目標点 t があれば,迂回路(を元のグラフに展開したもの)を出力して終わりで,
    • そうでなければ Cb に縮約して再帰する,

という非常にシンプルな構造でした.計算時間も \mathrm{O}(nm) となっていて,とても綺麗な結果でしたね.

*1:ブログとしてはちょうど一年ぶりの更新,わかりやすいですね.

*2:前提知識として,最短路問題に対する Dijkstra 法と,最大マッチング問題に対する Edmonds の花縮約アルゴリズムをなんとなく聞いたことがある,という程度を仮定します.

*3:E. W. Dijkstra: A note on two problems in connexion with graphs. Numerische Mathematik, 1 (1959), pp. 269–271. (DOI: 10.1007/BF01386390)

*4:枝長に関する計算(実数の四則演算や大小比較)は,基本演算として定数時間で実行できることを仮定します.

*5:このアルゴリズムは,優先度付きキューなどのデータ構造を用いて実装することで,より高速化できることも知られています.

*6:この問題は最短路問題(制約無し)を含んでいます.入力グラフで,s 周りの枝以外全てをそれぞれ長さ半分の直列枝 2 本で置き換えれば,任意の st パスの \ell に関する長さを保ったまま,それら全てを実行可能解にできます.

*7:U. Derigs: An efficient Dijkstra-like labeling method for computing shortest odd/even paths. Information Processing Letters, 21 (1985), pp. 253–258.  (DOI: 10.1016/0020-0190(85)90094-8)

*8:曲面として,トーラスやクラインの壺のようなものを想像してください.すると,その上の閉曲線で,どんな連続変形でも 1 点に潰せないようなものが取れるのがわかるかと思います.

*9:枝長に関する計算と同じく,ラベルに関する初等的な操作(群演算や要素の同一性判定,逆元の取得)は,基本演算として定数時間で実行できることを仮定します.

マトロイド共通基分割に関する反例

この記事は「反例」アドベントカレンダー 4 日目の記事です.本ブログは別のアドベントカレンダー用に昨日誕生したものですが,せっかくなのでもう 1 つぐらい記事を書いてみようと思います.

準備

色々言葉を準備しますが,そういうものかと適当に読み飛ばしていただいても大丈夫です.

  • G = (V, E)グラフであるとは,V が有限集合であり,E が「各要素が『要素数 2V の部分集合』であるような集合」であることをいう.ここで,V の各要素を頂点E の各要素をと呼ぶ.
  • グラフ G = (V, E)2 部グラフであるとは,頂点集合 V2 つの部分集合 UW に分割でき (\, U \cup W = V~~\text{and}~~U \cap W = \emptyset \,),各辺 e \in EU, W それぞれと非空な交わりを持つ (\, e \cap U \neq \emptyset \neq e \cap W \,) ことをいう.2 部グラフ G の頂点集合の分割を明示する場合,G = (U, W; E) と書く.
  • 辺部分集合 M \subseteq EGマッチングであるとは,「任意の頂点 v \in V に対して,v を含む M の辺が高々 1 本しかない」ことをいう.さらに |M| = |V|/2 が成り立つとき,M完全マッチングであるという.
  • 有限集合 E とその部分集合族 \mathcal{I} \subseteq 2^E = \{\, X \mid X \subseteq E \,\} の組 \mathbf{M} = (E, \mathcal{I})マトロイドであるとは,以下の 3 つの性質が成り立つことをいう.(本記事内では定義自体は特に重要ではなく,下の 2 つの例だけが必要になります.)
      (I0)  \emptyset \in \mathcal{I}.
      (I1)  X \subseteq Y \in \mathcal{I} \implies X \in \mathcal{I}.
      (I2)  [\, X, Y \in \mathcal{I}~~\text{and}~~|X| \lt |Y| \,] \implies \exists e \in Y \setminus X~~\text{s.t.}~~X \cup \{e\} \in \mathcal{I}.
    ここで,EM台集合\mathcal{I} の各要素を M独立集合と呼ぶ.さらに,包含関係に関して極大な独立集合をと呼び,マトロイド \mathbf{M} の基族を \mathcal{B}(\mathbf{M}) と書く.(I2) の性質から,X, Y \in \mathcal{B}(\mathbf{M}) \implies |X| = |Y| が導ける.
  • \mathbf{M} = (E, \mathcal{I})分割マトロイドであるとは,台集合 E の分割 E_1, \dots, E_r が存在して,独立集合族 \mathcal{I} が以下のように書けることをいう.\[\mathcal{I} = \{\, X \subseteq E \mid |X \cap E_i| \leq 1~(\forall i) \,\}.\]
  • \mathbf{M} = (E, \mathcal{I})グラフ的マトロイドであるとは,台集合 E を辺集合とするグラフ G = (V, E) が存在して,独立集合族 \mathcal{I} が以下のように書けることをいう.\[\mathcal{I} = \{\, X \subseteq E \mid X~は~G~中で閉路を形成しない \,\}.\]ここで,辺部分集合 X \subseteq E閉路を形成するとは,X の非空な部分集合 C であって,「各頂点 v \in V に対して,v を含む C の辺がちょうど 0 本または 2 本となる」ようなもの(閉路)が存在することをいう.

さて,ここから本題に入ります.以下の定理は 100 年以上前に示されたものですが,「自明な必要条件がそのまま十分条件にもなっている」というなかなか綺麗な結果です.

定理 (Kőnig)*1  任意の 2 部グラフ G = (U, W; E) と任意の正の整数 k に対して,以下は同値.

  • 辺集合 Ek 個の完全マッチングに分割できる.(\, \exists M_1, \ldots, M_k \colon G の完全マッチング~~\text{s.t.}~~\bigcup_{i = 1}^k M_i = E~~\text{and}~~[\, i \neq j \implies M_i \cap M_j = \emptyset \,] \,)
  • すべての頂点の次数が k である.(\, \forall v \in U \cup W,~d_G(v) := |\{\, e \in E \mid v \in e \,\}| = k \,)

そして,この定理をマトロイドの言葉で言い換えると以下のようになります.

  台集合 E が共通である任意の 2 つの分割マトロイド \mathbf{M}_1, \mathbf{M}_2 と任意の正の整数 k に対して,以下は同値.

  • 台集合 Ek 個の共通基に分割できる.(\, \exists X_1, \ldots, X_k \in \mathcal{B}(\mathbf{M}_1) \cap \mathcal{B}(\mathbf{M}_2)~~\text{s.t.}~~\bigcup_{i = 1}^k X_i = E~~\text{and}~~[\, i \neq j \implies X_i \cap X_j = \emptyset \,] \,)
  • \mathbf{M}_1, \mathbf{M}_2 それぞれに関して,台集合 Ek 個の基に分割できる.(\, \forall p \in \{1, 2\},~\exists X_1, \ldots, X_k \in \mathcal{B}(\mathbf{M}_p) ~~\text{s.t.}~~\bigcup_{i = 1}^k X_i = E~~\text{and}~~[\, i \neq j \implies X_i \cap X_j = \emptyset \,] \,)

というわけで,自然な疑問として,「上の系の分割マトロイドの部分を一般のマトロイドに置き換えるとどうなるのか?」ということが気になります.以下の反例は,k = 2 で,一方が分割マトロイド,他方がグラフ的マトロイドであるような場合でも,上の系が(そのままの形では)拡張できないということを示しています.

反例*2  K_4 = (V, E)4 頂点完全グラフ,すなわち,|V| = 4E = \binom{V}{2} = \{\, X \subseteq V \mid |X| = 2 \,\} であるグラフとし,M_1, M_2, M_3 \subseteq EK_4 の完全マッチングで互いに素なものとする.(必然的に M_1, M_2, M_3E の分割となる.)\mathbf{M}_1 = (E, \mathcal{I}_1)M_1, M_2, M_3 が誘導する分割マトロイド,すなわち,

\[\mathcal{I}_1 := \{\, X \subseteq E \mid |X \cap M_i| \leq 1~(\forall i) \,\}\]

とし,\mathbf{M}_2 = (E, \mathcal{I}_2)K_4 が誘導するグラフ的マトロイド,すなわち,

\[\mathcal{I}_2 = \{\, X \subseteq E \mid X~は~K_4~中で閉路を形成しない \,\}.\]

とする.今 k = 2 とすると,\mathbf{M}_1, \mathbf{M}_2 それぞれに関して,台集合 E2 個の基に分割できることは簡単に確認できる.一方,共通基は必ずどこか 1 頂点を含む辺 3 本すべてを取る必要があり,そのような辺部分集合の補集合は閉路となるため,E2 個の共通基に分割できないことがわかる.

*1:D. Kőnig: Graphok és Alkalmazásuk a Determinánsok és a Halmazok Elméletére. Mathematikai és Természettudományi Értesitő, 34 (1916), pp. 104–119. (Link: http://real-j.mtak.hu/4450/)

*2:cf. A. Schrijver: Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003. (ISBN: 9783540443896)

Double Counting による Erdős–Ko–Rado 定理の証明

この記事は「好きな証明」アドベントカレンダー 3 日目の記事です.*1

何かを数えるとき,数え間違いを防ぐために,複数の方法で数えてみるというテクニックがありますよね.数学でもこれに似た手法が使われることがあり,同じ対象を 2 通りの方法で数えることにより,その数を通じた関係式を導く技法を Double Counting と呼びます.

たとえば,簡単な例として,非負の整数 n に対して

\[\displaystyle\sum_{k = 0}^n \binom{n}{k} = 2^n\]

という等式を示してみましょう.ここで,\binom{n}{k}{}_nC_k とも書かれる二項係数で,「n 個の異なる物から k 個を選ぶ選び方の総数」に等しい値です.すると左辺は,その場合の数を,あり得る範囲のすべての k に関して足し合わせたものになっています.k の値が違えば同じ組合せが選ばれることも無いので,「n 個の異なる物からいくつかを選ぶ選び方の総数」を漏れなくダブりなく数えた式になっています.一方右辺は,「n 個の物それぞれに関して選ぶか選ばないか(2 通り)を決めることと,選ぶ物の組合せを決めることは同じである」という視点で,同じ場合の数を漏れなくダブりなく数えた式です.したがって,等式の両辺は,同じ対象を異なる方法で数えた式であるので,その値は等しいということが言えます.

では,もう少し非自明な主張を導いてみましょう.n 人の生徒が居るクラスの中で,k~(\le n/2) 人のチームをいくつか作りたいという状況を考えます.ただし,任意に 2 つのチームを選んだときに,架け橋となるような,両方に属する生徒が必ず 1 人は居るようにしたいとします.このとき,最大でいくつのチームを作ることができるでしょうか?
たとえば,どのチームにも属するような生徒を 1 人固定して,残りの (n-1) 人から (k-1) 人を選ぶすべての組合せでチームを作ることを考えると,\binom{n-1}{k-1} 個のチームを作ることができます.もっと多くのチームを作る方法はあるでしょうか?実は,そのような方法は存在しません.

定理 (Erdős–Ko–Rado)*2  正の整数 n, kk \le n/2 を満たすとし,S を要素数 n の集合とする.\mathcal{F}S の部分集合族 (\,X \in \mathcal{F} \implies X \subseteq S\,) であって,以下の性質をともに満たすとする.

  • X \in \mathcal{F} の要素数k である.(\,X \in \mathcal{F} \implies |X| = k\,)
  • 任意の X, Y \in \mathcal{F} の交わりは空でない.(\,X, Y \in \mathcal{F} \implies X \cap Y \neq \emptyset\,)

このとき,|\mathcal{F}| \le \displaystyle\binom{n-1}{k-1} = \frac{(n-1)!}{(n-k)!(k-1)!} が成り立つ.

証明   S の要素を円形に並べた円順列は (n-1)! 通りあり(回転して一致するものは同一視します),各円順列では,(*)「連続する k 個の要素からなる S の部分集合」が n 通り(どちら回りに見るかを固定すると,始点の選び方が n 通り)あります.以下では,あり得る円順列をすべて動かしたときに,\mathcal{F} の要素が (*) として出現する回数の総数を Double Counting することで,定理の主張を示します.

まず,各 X \in \mathcal{F} を固定したときに,X が何回出現するかを考えてみましょう.X の要素が連続していてほしいので,これらをひとまとめにしたブロックと,残りの (n - k) 個の要素で円順列を作ってみます.並べるものが (n - k + 1) 個なので,その総数は (n - k)! 通りです.ブロックの中で X の要素はどういう順番で並んでいてもよいので,それぞれに関して k! 通りずつ可能性があり,全体では (n - k)!k! 通りの円順列で X(*) として出現することがわかります.これは \mathcal{F} のどの要素でも全く同じことなので,総数は |\mathcal{F}| \cdot (n - k)!k! となります.

次に,各円順列を固定したときに,(*) のうち \mathcal{F} の要素がどれぐらい存在できるかを考えてみましょう.定理の 2 つ目の条件から,もしある X \in \mathcal{F}(*) として出現しているなら,他の \mathcal{F} の要素はそこからどちらかの向きに高々 (k - 1) 個分ずらした部分にしか (*) として存在できません.あり得る候補として,X からそれぞれの向きに i \in [k - 1] 個分ずらした (*) をそれぞれ Y_i, Z_i と書くことにしましょう.このとき,もし Y_i \in \mathcal{F} であったとすると,Z_{k-i} はそこからちょうど k 個分ずれた位置にあり,逆向きにも n - k~(\ge k) 個分ずれているので,Y_i \cap Z_{k-i} = \emptyset が成り立ちます.すなわち,各 i について,Y_iZ_{k-i} の高々一方しか \mathcal{F} に属せないため,(*) のうち \mathcal{F} の要素となっているものは,X を含めて高々 k 個しか無いことがわかります.これはどの円順列でも全く同じことで,あり得る円順列は (n-1)! 通りであったので,総数は高々 (n-1)!k であることがわかります.

最後に,上の 2 つの段落で Double Counting した対象は同じ(あり得る円順列をすべて動かしたときに,\mathcal{F} の要素が (*) として出現する回数の総数)であったので,
\[|\mathcal{F}| \cdot (n - k)!k! \le (n - 1)! k\]
という関係が得られ,これを変形すると
\[|\mathcal{F}| \le \frac{(n - 1)!}{(n - k)!(k - 1)!} = \binom{n - 1}{k - 1}\]
となり,定理の主張が示せました.(Q.E.D.)

本証明は,Katona (1972) による論文*3を参考にしています.

*1:この記事を書くために Hatena Blog を始めました.今後記事が増えるかどうかは未定です.

*2:P. Erdős, Chao Ko, R. Rado: Intersection theorem for system of finite sets. Quarterly Journal of Mathematics, Oxford Series, 12 (1961), pp. 313–320. (DOI: 10.1093/qmath/12.1.313)

*3:G. O. H. Katona: A simple proof of the Erdős–Chao Ko–Rado theorem. Journal of Combinatorial Theory, Series B, 13 (1972), pp. 183–184. (DOI: 10.1016/0095-8956(72)90054-8)