数学の組合せ論において、エルデシュ・コー・ラドの定理（Erdős–Ko–Radoの定理、）とは、交叉集合族（構成する全ての集合のいずれの2つにおいても1つ以上の元を共通して持つような集合族）をなす集合の数の上限を与える定理である。ポール・エルデシュ、、によって1938年に証明され、1961年に発表された。における中核的な研究成果の一つである。
この定理が適用されるのは、構成するすべての集合が等しく 個の元を持ち、かつ、それらの集合がすべてある 元集合の部分集合であるような集合族である。例えば、 個の元から一つを選び、その元を含む 元部分集合全てからなる集合族はこの条件を満たす。エルデシュ・コー・ラドの定理は、問題が非自明となる においてこの構成方法が最大の交叉集合族を与えることを主張する。さらに、 の場合は他にも最大の集合族を構成する方法があるが、 の場合はこの構成方法で得られる集合族のみが最大の交叉集合族となる。
エルデシュ・コー・ラドの定理はハイパーグラフやクネーザーグラフの独立集合の用語で読み替えることができる。また、集合に代えて線型部分空間や置換、文字列などの他の種類の対象に適用される類似の定理もある。それらもまた、ある要素を選び、それを含む全ての対象からなる族が最大の交叉族となることを示すものである。
定理の主張 を以下の条件を満たす集合族とする： 構成する集合はすべて 個の元を持ち、 のある 元集合の部分集合である。 構成する集合のどの二つも、必ず1つ以上の元を共有する。 このとき、エルデシュ・コー・ラドの定理は を構成する集合が高々 個であることを主張する。 の条件はこの問題が非自明であるために必須であり、 の場合はそもそも 元集合の 元部分集合がすべて互いに交叉するので、最大の交叉集合族は 元部分集合の全体となり、そのサイズは となる; , p. xiii.。
同じ内容をハイパーグラフの理論の一部としても定式化できる。 元集合を頂点集合、集合族をハイパーグラフと捉えるとき、集合族を構成する集合（ハイパーエッジ）のサイズが等しく であるので、これは -一様ハイパーグラフになる。したがって、エルデシュ・コー・ラドの定理は のもとで 頂点の -一様ハイパーグラフにおける互いに重なるハイパーエッジの個数の上限を与えるものになる。
エルデシュ・コー・ラドの定理はグラフ理論の用語でも定式化できる。 元集合の 元部分集合それぞれを頂点とし、互いに素である集合の間に辺を持つグラフはクネーザーグラフと呼ばれる。また、グラフにおいていずれの間にも辺の無いような頂点の集合を独立集合といい、そのグラフにおいて最大の独立集合のサイズを独立数という。これらを用いると以下のように言い換えられる; , p. xiv.。 のもとでクネーザーグラフ の独立数は である。
また、クネーザーグラフは頂点推移グラフであり、は頂点数を独立数で割った値に等しい。したがって、エルデシュ・コー・ラドの定理の系としてクネーザーグラフ の分数彩色数は となる。
歴史 ナチスの影響を避けるためにハンガリーからケンブリッジ大学に移ったポール・エルデシュとベルリンからケンブリッジ大学へ移った、そして当時マンチェスター大学でルイス・モーデルに師事していたの3人は、イギリスでの共同研究を経て1938年にこの定理を証明した。しかし、この成果が出版されたのは1961年のことだった。この長い遅れには、1930年代当時に組合せ集合論への関心が低く、1960年代になって高まってきた背景がある。1961年の論文で示された成果は先述の主張よりも一般的なもので、集合族をなす各部分集合のサイズは「高々」 で、それらの間に包含関係が無いことを前提としていた; .。このような集合族は、ホールの結婚定理を繰り返し適用することですべての部分集合のサイズを まで拡大し揃えることができる。あるいは、もとの 元集合の部分集合間の包含関係がなすブール束における対称鎖分解を利用し、同じ鎖のサイズ の集合に取り換えることでもサイズを に揃えることができる。
交叉集合族の最大と極大 最大の交叉集合族
エルデシュ・コー・ラドの定理による上限値のサイズを持つ交叉族を構成する簡単な方法は、 元集合の元ひとつを として任意に選び、 を含む 元部分集合を全て集めることである。例えば、 かつ の場合、4元集合 について、 とすれば、 という集合族が得られる。この中のいずれの2つの集合も、という共通の元を持つので交叉している。この方法で交叉族を構成すると、 以外の元 個の中の 個組ごとに を加えて 元集合とするので、交叉族のサイズは となる。
の場合、上限サイズに到達する交叉族はこのような集合族のみである。しかし、 の場合は、より一般の構成方法が存在する。 元集合の 元部分集合は、互いに補集合となるペアごとに分割することができる。このとき、各部分集合は、自身の補集合とは互いに素であるが、それ以外の全ての部分集合と交叉することに注目すると、各ペアからそれぞれ一方を選んで構成される集合族は交叉族になる。そのサイズはペアの数に等しく、 である。例えば、4元集合 の場合、 と 、 と 、 と 、の3つのペアがあり、それぞれ後者をとることで という交叉族が得られる。これは先の構成方法とは異なり、全ての部分集合に共通する元は存在しない。
なお、 の場合、先に述べた通り最大の交叉族は必ず共通元を持つが、これは英語ではstars、dictatorships、juntas、centered families、principal familiesなどと呼ばれる。また、最大に近いサイズの交叉族も、構成する集合のほとんどに共通な元があり; ; .、この性質は安定性（stability）と呼ばれることがある。ただし、この用語は他の意味でも使われることがあり、例えばクネーザーグラフからランダムに辺を取り除いても独立数が増加しないという事実を指す場合にも用いられる; .。
極大の交叉集合族
元集合からなる交叉族は、その性質を損なうことなしに、（たとい土台となる集合に新たな元を加えて拡張し、 を増やしたとしても）それ以上の集合を追加できないという意味で極大である可能性はあるが、必ずしも最大サイズであるとは限らない。、 の場合の例として、の7本の直線の集合が挙げられるが、これはエルデシュ・コー・ラドの定理の上限値である15を大きく下回る。より一般に、位数 を持つ任意の有限射影平面の直線は、 かつ の場合、 個の集合のみを含む最大交叉族を形成する。ファノ平面はこの構成における の場合である。
元集合からなる極大交叉族の最小サイズは、一般の に対して明らかになってはいないものの、 において 以上である。射影平面は 個の集合からなる極大交叉族を与えるが、無限に多くの において、それよりも小さなサイズ の極大交叉族が存在する。
元集合からなる、最大ではないが極大となる交叉族の最大サイズは、 である。このような交叉族は、 元集合のある元 を含まない 元部分集合 を用意し、「 を含み と交わらない 元部分集合」の全体に を加えることで構成される。この成果はとによって1967年に証明されたもので、ヒルトン・ミルナーの定理と呼ばれる; ; , Section 1.6: The Hilton–Milner theorem, pp. 15–17.。
証明 エルデシュ・コー・ラドの定理のオリジナルの証明は についての数学的帰納法を用いた。起点となる の場合については、いかなる交叉族もある集合とその補集合を同時に含むことができないという事実から、上限が 元部分集合の総数のちょうど半分であることが容易に示せる。より大きな への帰納法のステップでは「shifting」と呼ばれる手法を使用する。これは、交叉族内で集合を「寄せる」ことで、「この集合が交叉族に入っているのなら、より「寄せた」集合も入っている」という性質を利用して、 元集合の 元部分集合からなる交叉族と 元集合の 元部分集合からなる交叉族の問題に帰着させる; , Section 1.1: The original proof, pp. 2–6.。
1972年にはを使用して以下の短い証明を与えた; ; ; .。
元集合の 元部分集合からなる交叉族 が与えられたとする。 個の元の全ての巡回順序 にわたって の各集合 と同じ元で構成される長さ の区間を数え上げる、言い換えれば、集合 が区間として巡回順序 に現れるようなペア を数え上げるのが証明の基本戦略である。例えば、 かつ で 元集合が の場合、 はその巡回順序のひとつである。この巡回順序の中の長さ の区間は、 、、、、、、、 の8つである。
まず、各集合 ごとにが巡回順序全体で現れる回数を数え、 全体で合算することで数え上げる。 の元が連続して並ぶ巡回順序は、 の各元の並び方 通りと残りの元の並び方 通りを任意に組み合わせたものであり、各順序について の区間はただ一つなので、 全体で合算すると 回である。
次に、各巡回順序 ごとに交叉族を構成する集合が区間として現れうる回数を数え、巡回順序全体で合算することで上から評価する。 は交叉族なので、構成する集合が巡回順序 に区間として現れるときも全て互いに交わらなければならない。そこで、巡回順序 の長さ の区間の集まりで、いずれの2つも交わるようなものを考えると、 という条件から、 個までしか区間をとることができない。というのも、ある区間（先の巡回順序の例で例えば ）から、一つずつ先の区間をとると、 個先（）まではそれまでのすべての区間と重なるが、その次の区間（）の始点は最初の区間の終点よりも先であり、また、 であることからこの区間の終点は最初の区間の始点に届かないからである。それゆえ、各巡回順序 ごとに 回まで、巡回順序全体で合算しても高々 回である。
以上により、 と評価できて、 という上限値が得られる。
エルデシュ・コー・ラドの定理は、これまたの重要な成果の一つであるの特別な場合として導出することも可能であり、他にも多くの証明が知られている; , p. 22.。
定理の派生 一般化 この定理の一般化のひとつは、部分集合間の共通部分に一定以上のサイズを要求するものである。この場合にはパラメータは3つとなる。元の総数 、部分集合のサイズ 、そして、任意の2つの部分集合の共通部分の最小サイズ である。元々のエルデシュ・コー・ラドの定理は の場合である。他の2つのパラメータに対して が十分に大きければ、-交叉族のサイズは高々 である; , Theorem 0.0.2, p. xiv.。この上限値が成り立つのは正確には においてであり、これより小さい では成り立たない。なお、 であれば、このサイズの -交叉族は、全ての部分集合が共通して持つ 個の元を指定し、その 個の指定された元を含む全ての 元部分集合の族を構成することによってのみ得られる。一方で、 の場合の -交叉族のサイズの上限は、とレヴォン・H・ハチャトゥリアンによって、として特定された。
この一般化に対応するグラフ理論での定式化はクネーザーグラフに代えてが関係する。十分大きな 、特に において、エルデシュ・コー・ラドの定理とその一般化は独立数に留まらず、に及ぶ強力な結果をもたらす。すなわち、-交叉する 元部分集合に対応するジョンソングラフのシャノン容量は である; .。
また、エルデシュ・コー・ラドの定理はどの 個の部分集合も共通部分を持つ集合族について一般化することができる。元々の の定理で全ての部分集合に共通する元を持たせることができたように、十分大きな についてオリジナルの定理と同じく上限は だが、「十分大きな」の範囲は から に広がる; .。
類似の命題 有限集合以外の対象のクラスについて、エルデシュ・コー・ラドの定理と類似した多くの結果が知られている。これらは総じて、ある交叉の定義のもとで、「交叉する対象の最大の族は、ある要素を選び、その要素を含むすべての対象の族を構成することによって得られる」という主張を含む。例としては、次のようなものがある：
一つは、有限体上の線型部分空間の交叉族に関する -類似である。 を、位数 の有限体上の 次元ベクトル空間における 次元部分空間の交叉族とし、 とする。このとき となる。ここで は -二項係数で、位数 の有限体上の 次元のベクトル空間内の 次元部分空間の個数を表す。上限に達する最大の交叉族は、任意の非零ベクトルを選び、そのベクトルを含む 次元部分空間すべてからなる族を構成することで得られる; , Chapter 9: The Grassmann scheme, pp. 161–183.。
同一集合上の2つの置換は、両方の置換で同じ像を持つ元が存在する場合、交叉するものと定義される。 元集合においては、 個の交叉する置換からなる族が存在する。これは、元の一つを固定する置換（その元の安定化部分群）である。これに対応する定理として、交叉する置換の族はこれより大きくなることはなく、また、サイズ の交叉置換族は、ある元の安定化群の剰余類（すなわち、特定の元を特定の元に写す置換全体の族）のみであることが挙げられる。より一般に、任意の および十分に大きな に対して、どの2つも 個の元で値が等しい置換の族の最大サイズは であり、このサイズの族は特定の 個の元全てについての安定化部分群の剰余類のみである; ; ; ; ; , Chapter 14: Permutations, pp. 260–278.。あるいは、グラフ論の用語を用いれば、 元の置換は完全二部グラフ の完全マッチングに対応し、この定理は、各ペアが 本の辺を共有する完全マッチングの族のうち最大サイズのものは、 本の指定された辺を含むマッチングの全体であることを述べている。また別の類似の一つは集合の分割に関するものであり、完全グラフ （ は偶数）の完全マッチングが特殊ケースとして含まれる。完全マッチングの総数は二重階乗 を用いて である。互いに交叉する（共通の辺を持つ）マッチングの最大の族のサイズは であり、これは一辺を固定し、残りの 頂点を組み合わせるすべての方法を選択することで得られる。
は、有限個の抽象的な点と直線からなる構造体系で、全ての点が同数の直線に属するなどのいくつかの公理を満たすものである。partial geometryにおいて、任意の一点を通る直線の集合から互いに交叉する直線の最大の族を得ることができる。
は一つの集合と、その各元を または に対応付ける写像からなる。2つの符号付き集合は符号も等しい共通の元を持つとき、交叉するという。このとき、 元の宇宙において 元符号付き集合からなる交叉族は高々 個の符号付き集合で構成され、この上限値のサイズの族は一つの元と符号を固定し、残りの 個の元および符号を任意にとることで得られる。
サイズ のアルファベットからなる長さ の文字列 について、2つの文字列が同じ位置に共通の文字を持つ場合、それらは交叉すると定義できる。最大の交叉族は、1つの位置を選び、その位置に固定の文字を割り当て、残りの位置の文字を任意に変化させることによって得られる。これらの族は 個の文字列からなり、このサイズでどの2つとも交叉する文字列の族はこれらのみである。より一般に、任意の2つの文字列が 箇所で同じ文字を持つ最大規模の文字列族は、、、および に応じた を用いて 箇所とその各位置に1文字を設定し、少なくともそのうち 箇所で設定された文字を持つ文字列の族を構成することで得られる。これらの結果は、を用いてグラフ論的に解釈することができる; , Chapter 10: The Hamming scheme, pp. 184–209.。
とカレン・ミーガーによって提唱された未解決の予想は、 個の頂点を持つ凸多角形の三角形分割の族に関する別の類似に関するものである。すべての三角形分割の数はカタラン数 であるが、この予想によれば、任意の2つの三角形分割が辺を共有する三角形分割の族の最大サイズは である。サイズ の交叉する三角形分割の族は、多角形の頂点の一つを三角形で切り取り、残りの 頂点を持つ多角形を三角形分割するすべての方法を選ぶことで得られる。
応用 エルデシュ・コー・ラドの定理を用いると、確率論において以下の結果を証明することができる。 を、1となる確率が である独立な0-1確率変数とし、 をこれらの変数の任意に固定された凸結合とする。このとき、 となる。この証明では、の凸結合の値が1/2以上になるような変数の部分集合は互いに交わるものでなければならないという事実を観察し、エルデシュ・コー・ラドの定理を用いてこれらの部分集合の数の上界を与える; .。
エルデシュ・コー・ラドの定理の安定性に関する性質は、クネーザーグラフの（彩色になっているとは限らない）頂点着色における単色辺を見つけるための効率的なアルゴリズムにおいて重要な役割を果たしている。また、エルデシュ・コー・ラドの定理は、系統樹の空間の対称性を特徴づけるためにも用いられている。
関連項目 ヘリーの定理：交叉する凸集合の族が共通の交わりを有することを保証する条件 ：互いに包含関係の無い集合族についての上限 シュタイナーシステム：大きな共通部分を持つようなペアがいない最大サイズの一様集合族 ：どの2つの集合も同じ共通部分を持つ集合族 予想：交叉する辺の族のサイズについての未解決問題
脚注 出典
参照文献
外部リンク