シルヴェスター–ガライの定理（シルヴェスター–ガライのていり、）は、幾何学において、平面上の有限個の点のうち、ちょうど2点のみを通るまたはすべての点を通る直線が存在する事を示す定理。1893年にこの問題を提起したジェームス・ジョセフ・シルヴェスターと、1944年に最初の証明を発表したティボル・ガライに因んで命名された。

平面上の有限個の点のうち、ちょうど2点のみを通る直線は と呼ばれる。シルヴェスタ–ガライの定理を別の方法で表現すると、平面上の有限個の点であって少なくとも1つの点が他の2点と共線でなければ、その有限個の点の集合は ordinary line を持つ、となる。より強い定理によれば、（すべての点が一直線上にある、ということがない）有限個の点の集合には、線型数以上の ordinary line が存在する。ordinary line を発見するアルゴリズムの時間計算量は、点の集合に対してである。

 歴史 
シルヴェスタ–ガライの定理は、 によって提起された。 は、シルヴェスターは上の三次曲線の9つの変曲点が、9点と12直線の（）を成すという代数幾何学の問題に触発されたことを示唆している。シルヴェスター–ガライの定理はこの9つの変曲点がすべて実座標を持つことは不可能であることを示している。

 は、シルヴェスター–ガライの定理の短い証明を発見したと主張したが、発表する時点ですでに、証明が不完全であることが指摘されていた。 は、定理の射影幾何学的な双対を示すことで、正確で強力な定理を得た。 は、メルヒオールの証明に気づかぬまま、定理を予想として述べ、 その後にティボル・ガライや他の数学者が証明した。

1951年の評論では、エルデシュは「ガライの定理」の名を使用した。1954年には、の評論で「シルヴェスター–ガライの定理」という名称が使われた。

 同値な定理 
ordinary line の存在問題は、ユークリッド平面の代わりに射影平面で考えることで、ordinary line の双対となる点の問題としても考えることができる。射影平面は通常のユークリッド平面上の点に"無限遠"を付加することで構築される。しかし、無限遠に付加された点は、ordinary line を持たない点の集合を作るのに役立つわけではない。射影平面上の任意の有限個の点が、点と直線の接続関係の同様の組み合わせパターンを持つユークリッド点の集合に変換されるためである。したがって、ユークリッド平面と射影平面のどちらかに存在する交点と直線のパターンは、もう一方の平面にも存在する。にもかかわらず、射影的な観点によって点と直線の配置を簡単に述べることができる。特に、を使用することができることが重要である。この双対性の下、ordinary line の存在は、非自明な配置の有限個の直線上の、上の有限個の点（）の存在に置き換えることができる。ここで直線の配置が自明であるとは、すべての直線が共点であることで、非自明であるとは、ある ordinary point がちょうど2直線に属する状態を示す。

直線の配置はゾーン多面体（と呼ばれる直線の有限集合のミンコフスキー和から成る多面体）と近い組み合わせ的構造を持つ。この関係において、ゾーン多面体の対面の組は、射影平面上の直線の配置の交点と各 generator に対応する。対面の組の個数は、交点の数の2倍である。

例えば、長菱形十二面体は5本の generator を持つゾーン多面体で、六角形の対面の組が2つ、平行四辺形の対面の組が4つ存在する。5本の直線の配置の対応において、3直線の組の2つが交差し、六角形の対面に対応する。また、残りの直線は ordinary point で交差し、平行四辺形の対面の組に対応する。ゾーン多面体の観点から、シルヴェスター-ガライの定理を言い換えると、すべてのゾーン多面体は1つ以上の）平行四辺形を持つ、となる。より強力には、平面上の点の集合は少なくとも個の ordinary lines を持ち、 本の generator を持つゾーン多面体は少なくとも個の平行四辺形の面を持つことが保証される。

 証明 
シルヴェスター-ガライの定理はさまざな方法で証明されてきた。ガライの1944年の証明は、ユークリッド幾何学と射影幾何学を交互に切り替えて、点を傾きが0に近い ordinary line に変換するというものである（詳しくはを参照されたい）。1941年のメルヒオールの証明では、射影幾何学の双対性を用いて、問題を直線の配置に置き換え、オイラーの多面体公式を使った。の証明は、0でない最小の距離にある点を繋ぐ直線は ordinary になることを背理法によって示した。またスタインバーグ（Steinberg）の早期の証明に続いて、コクセターは、傾きの計量と、ガライとケリーの証明に現れた距離の概念を不必要とする代わりに、の公理を使った定理のみを使用して証明した。

 ケリーの証明 
次はによる証明である。 はケリーの証明を、数多の証明の中で"simply the best"であると述べている。

を共線でない点の有限集合とする。少なくともの2点を含む直線を、connecting line と定義する。の有限性より、の要素には点と connecting line の距離が最小となるような点が存在する必要がある。ケリーはこのときの connecting line が ordinary であることを背理法によって証明した。 

を ordinary でないと仮定しよう。は少なくともに属する3点以上を通る必要がある。これら共線点のうち2つ以上は、へのの直交射影に関して同じ側にある。この2点をと定義する。ただし、はこの順で並んでいるとする。をを通る connecting line、をのへの直交射影とすれば、が相似かつであることより、はより短い。

しかし、これはの定義に矛盾する。これはが ordinary でないとした仮定が偽であることを意味する。よって題意は示された。

 メルヒオールの証明 
1941年（エルデシュの問題発表とガライの証明の前）、メルヒオールは、射影平面上の非自明な直線の配置は、3つ以上の ordinary point を持つことを示した。双対性より、非自明な点の集合は3つ以上の ordinary line を持つことを意味する。

メルヒオールは、射影平面に任意のグラフについて、オイラー標数は1でなければならないことに気づいた。ここで、はそれぞれ、グラフの頂点、辺、面の個数。射影平面上の非自明な直線の配置は、面は3辺以上で囲まれ、辺は2面で囲まれるようなグラフを定義する。そのため、ことで不等式を得る。この不等式によって、オイラー標数からを取り除くことよりが証明できる。しかしもし、配置上のすべての頂点が3以上の直線の交点であるならば、辺の総数は以上であるが、これは不等式に矛盾する。したがって、いくつかの頂点は2直線のみの交点でなければならず、メルヒオールの慎重な分析が示すように、3個以上の ordinary vertice が少なくとも不等式を満たす必要がある。 

 の指摘のように、ordinary vertex の存在に関する議論は、1944年、によって与えられた。スティーンロッドは ordinary line の問題の双対を明示的に応用した。

 メルヒオールの不等式 
同様の議論で、メルヒオールはより一般的な結果を証明することができた。任意のにおいて、を本の直線で作られる点の個数として、次の式が成立する。。

 

同値な表現として次の形でも表すことができる。

 

 公理数学 
 はケリーの証明のユークリッド距離の使用は不必要に強力で、"like using a sledge hammer to crack an almond"（アーモンドを砕くために大型ハンマーを使うようなものだ）と述べた。 代わりにコクセターは順序幾何学において証明を行った。コクセターの証明は1944年のスタインバーグによって与えられた証明の変形である。最小の公理集合を見つける問題は逆数学の定理を証明する必要がある。詳細はこの問題に関する研究のを見よ。

シルヴェスター-ガライの定理の通常の主張はにおいては有効でない。構成幾何学で拒否される排中律の弱いものであるLPOを意味するためである。にもかかわらず、構成解析の公理の範囲のシルヴェスター-ガライの定理の定理は定式化が可能で、ケリーの証明を構成幾何学の公理の下で、有効となるように適用することができる。

 ordinary lineの捜索 
ordinary line の存在のケリーの証明では、2点を通る直線と点の距離が最小となるような組を見つける事で ordinary line を見つけることができる。 はこの方法で力まかせ探索を用いて ordinary line を捜索する時間計算量はであることを報告した。 しかし、はで発見するアルゴリズムを開発した。これは、集合の中の3点からなる三角形で最小のものを探すことの副産物であった。彼らの同様の論文にて、（メルヒオールとスティーンロッドの証明を用いて）、双対の配置で ordinary point を見つける方法が同様の時間であることを示した。 は最初に（ケリーの証明を必要としない方法で）1つのordinary lineを発見する時間の方法を開発した。同じ時間ではあるがより単純なアルゴリズムがによって述べられている。

のアルゴリズムはコクセターの証明をもとにしている。次の手順で示される。

 与えられた点の凸包の頂点から点を選ぶ。
 直線を、と他の凸包の頂点を通る直線として構築する。
 他の与えられた点をと成す角で並べ替え、同じ角のものをグループ化する。
 グループ内のある点が孤立していれば、その点とを通る直線が ordinary である。
 それぞれの2つの連続するグループに対して、2直線を、一方のグループ内のと最も近い点と、もう一方の最も近い点を通る直線とする。
 このようにしてできた直線の集合内のそれぞれの直線に対して、との交点を取る。
 この交点がと一番近いようなが ordinary line となる。

著者らの証明のように、このアルゴリズムで ordinary line を必ず見つけることができる。4つ目のステップで見つかった場合は構成幾何学によるもの、7つ目のステップで見つかったものは背理法によるもので、もし7つ目の段階で見つかったものが ordinary line でなければ、交点らと を通る直線が ordinary line として存在するが、これは4つ目の段階で発見されるべきものである。

 ordinary lineの個数 

シルヴェスター-ガライの定理は点の配置について ordinary line の存在は述べているが、ordinary line の個数については述べていない。をつの共線でない点の集合のordinary lineの最小の個数とする。メルヒオールの証明ではが示された。 はが増えるにつれては無限大へ発散していくと考えた。 はを証明して、予想が正しいことを示した。 はを予想した。これは現在ディラック–モツキン予想（Dirac–Motzkin conjecture）と呼ばれている（詳細はを参照）。 は を証明している。

ディラックの予想した下限は漸近的には最もよいもので、4超過の偶数の上限と対応する。Károly Böröczkyによる上限を達成した構築は、射影平面上の正角形の頂点と頂点の組で決定される方向の無限遠点個（延べ個）から構築される。これらの点の組は個あるが、個のみの方向を決定する。この配置では個の ordinary line を持ち、頂点とそれに隣り合う2頂点と共線な無限遠点を結ぶ点になる。実射影平面の任意の有限の配置のように、この構成は ordinary line の数を変えずにすべての点が有限点となるように帰ることができる。

奇数において、ディラックの予想の下限に一致する例は2つしか知られていない。1つはの考案した正三角形の頂点、重心 、辺の中点の7点から成る構成である。この7点は ordinary line を3つのみ持つ。3つの ordinary line を持つはユークリッド平面上では単一の直線に置き換えることはできないが、として知られる有限の射影空間を構成する。この接続関係のために、ケリー-モザーの例は non-Fano configuration としても呼ばれる。他の例にマッキー（McKee）の考案した 、1辺を共有する2つの正五角形の頂点と、共有辺の中点と4つの無限遠点の延べ13点から成る配置がある。これは6つの ordinary line を持つ。Böröczky の構成を修正すれば、奇数n個の点で個の ordinary line を持つ配置が導かれれる。

 はが7である場合を除き、 が成立することを証明した。漸近的には、証明された上限のである。 の場合、ケリー-モザーの例が反例となって除外される。しかし、Csima–Sawyerの境界がにおいても有効だったならば、が主張されただろう。

似た結果にがある。これは少数の点の直線の数と一本の直線上の点の数が対応されることを延べている。

ベン・グリーンとテレンス・タオは、十分大きい点の集合に対して（適当にを選択したときとなるようにして）、ordinary line の数は確かに少なくともとなること示した。更に、 が奇数ならば、ordinary line の数はある定数が存在して少なくともとなる。したがって、Böröczky による構成は最良であったことが判明した。ordinary line の個数の最小化は、グリーンとタオが十分大きい場合について証明した、3点を通る直線の個数の最大化問題である Orchard-planting problemにも深く関係している。ordinary point を探すような双対の状態において、擬似直線の配置の ordinary point の最小を考えることができる。この場合においては、Csima-Sawyerのの下限は有効であるが、グリーンとタオの漸近的な境界が有効であるかは知られていない。

 connecting lineの数 
ポール・エルデシュの気づきのように、シルヴェスター-ガライの定理は共線でない点の集合について少なくともつの異なる直線が決定できることを意味する。 この結果はとして知られる。基本的な場合としては、の場合が自明である。値の大きいについては、 （残りの点がすべて共線とならないように注意して）1本の ordinary line とその直線上の2点のうち1点を削除して、点を点に減らすことができる。よって、定理は数学的帰納法から示すことができる。ニアペンシル（near-pencil）と呼ばれる個の共線点と、それらと共線でないある1点から成る配置が下限の例となる。

 一般化 
シルヴェスター-ガライの定理は、ユークリッド平面平面上の色付きの点の集合や、代数的または距離空間的に定義される点と直線の系に一般化できる。より一般にはこれら定理のバリエーションは、ordinary line を持たない点の集合を避けるため、有限集合に対するものとなっている。

 色付きの点 
色付きの点におけるシルヴェスター-ガライの定理は、1960年代中期にロナルド・グラハムが提起し、が広めた。 2つの色に分けられた（すべてが同一直線上にはない）有限の点の集合について、2つ以上のすべて同色の点を通る直線が存在するかどうかを考える。 集合と集合族の言葉では、（すべてが同一直線上にはない）有限の点の共線部分集合の族はを持つことはできない、と表現できる。証明はによって発表されたが、公表はされなかった。最初に証明を公表したのはである。

 非実座標 

ユークリッド平面または射影平面が実数の組、座標を用いて定義できるように（ユークリッド平面は直交座標系、射影平面は）、 点と直線の系の抽象的な類似物は、数と座標を用いて定義できる。シルヴェスター-ガライの定理は有限体上でこのように定義された幾何学では適応できない。つまりのような有限幾何学において、すべての点の集合の ordinary line は存在しない。

また、シルヴェスター-ガライの定理は複素数や四元数の組の座標を持つ幾何学においても直接は成立しないが、より複雑な類似物であれば成立する。例えば、には、9つの点（三次曲線の変曲点）の配置であるがある。この配置における ordinary line は存在しない。このような配置は、として知られ、ユークリッド平面上では成立することはない。 シルヴェスター-ガライの定理の他の方法で述べると、シルヴェスター-ガライ配置が共線性を保ちつつユークリッド平面に埋め込まれるとき、配置内の点は常に一本の直線上にある、となる。したがってヘッセ配置の例は、では偽であることが分かる。 しかし、はシルヴェスター-ガライの定理の複素数への類似物として、 を複素射影平面に埋め込んだ時、すべての点は2次元部分空間上になければならないことを示した。つまり、 アフィン包が全体の空間であるような3次元複素空間上の点の集合は必ず1つの ordinary line を持ち、また ordinary line の線型数を持たなければならない。同様に、 は四元数で定義される空間に埋め込むとき、それらの点は必ず3次元部分空間上になければならないことを示した。

 マトロイド 
ユークリッド平面上の点の任意の集合とそれらを繋ぐ直線は、ランク3のの成分と平面に抽象化される。実数でない数の体系で定義される幾何学の点と直線はマトロイドを成すが、必ずしも有向マトロイドを成すわけではない。この状況において、の ordinary line の個数の下限の結果は、有向マトロイドへ一般化できる。ランク3の成分の有向マトロイドは、個の、2点を通る直線を持つ。あるいは、より少数の2点を通る直線の持つランク3のマトロイドは無向である必要がある。 2点のみを通る直線がないようなマトロイドはと呼ばれる。関連して、7点と3つの ordinary line を持つケリー-モザー配置は、におけるを構成する。

 距離幾何学 
シルヴェスター-ガライの定理の他の一般化において、によって任意の距離空間へ予想が行われによって解決された。この一般化では、距離空間上の3点が三角不等式の等号を満たすとき共線であると定義され、直線は、既に直線上にある2点と共線である点の全体の集合であると定義された。ChvátalとChenによる一般化はすべての有限距離空間は、すべての点を含むような直線かただ2点のみを通る直線を持つことを示した。