ベックの定理（幾何学）

離散幾何学において、ベックの定理はいくつかの異なる結果のいずれかであり、そのうちの2つを以下に示す。両方とも、他のいくつかの重要な定理とともに、 József Beckの有名な論文に掲載されている。^{[1]以下で説明する2つの結果は、主に平面上の点の集合によって}決定される直線の数の下限に関するものである。（点集合の少なくとも2つの点を含む直線は、その点集合によって 決定されると言われる。）

エルデシュ・ベックの定理は、LM KellyとWOJ Moser ^[2]による古典的な結果のバリエーションであり、0 < k  <  O ( √ n )に対して、 最大でn − k個の点が 共 線的である配置に関するものである。彼らは、 nがkに対して十分に大きい場合、配置は少なくともkn  − (1/2)(3 k  + 2)( k  − 1)本の直線に広がることを示した。 ^[3]

Elekes と Csaba Toth は、エルデシュ・ベックの定理は高次元に簡単に拡張できないことを指摘しました。^[4]たとえば、 2 本の斜めの直線上にあるR ³の2 n個の点の集合を考えます。これらの 2 本の直線はそれぞれn個の点に接していると仮定します。このような点の構成は 2 n平面にしか広がりません。したがって、 R ^dの点集合に対する仮説を単純に拡張するだけでは、目的の結果を得るのに十分ではありません。

この結果はエルデシュによって最初に推測され、ベックによって証明されました。（^[1]の定理5.2を参照）

S を平面上のn点の集合とする。0 ≤ k  <  n − 2の任意の直線上に n  −  k点以下が存在する場合、 Sの点によって決定される Ω( nk ) 本の直線 が存在する。

ベックの定理によれば、平面上の点の有限集合は、2 つの極端な状態のいずれかに分類されます。1 つは、点の大部分が 1 本の線上に存在する状態、もう 1 つは、すべての点を結ぶのに多数の線が必要になる状態です。

ベックの論文では言及されていないが、この結果はエルデシュ・ベックの定理によって示唆されている。^[5]

この定理は、平面上の任意のn点に対して、次の文の少なくとも 1 つが真となるような 正の定数C、Kが存在することを主張します。

1. 少なくともn / C個の点を含む直線が存在します。
2. 少なくとも 本の線が存在し、それぞれの線には少なくとも 2 つの点が含まれています。${\displaystyle n^{2}/K}$

Beck の元の議論では、Cは 100 で、K は指定されていない定数です。つまり、CとKの最適値は不明です。

ベックの定理の証明は次のように与えられます。平面上のn 個の点の集合P を考えます。j は正の整数とします。集合P内の点のペアA、B は、 AとBを結ぶ線がPの点と点( AとBを含む)の間を含む場合、 j 連結であるとします。 ${\displaystyle 2^{j}}$${\displaystyle 2^{j+1}-1}$

セメレディ・トロッターの定理より、このような直線の数は で、次のようになります。n個の点の集合Pと、少なくともPの点を含むPの点のペアによって張られるすべての直線の集合L を考えます。2 つの異なる直線 上には 2 つの点はあり得ないので、セメレディ・トロッターの定理を使用すると、 PとL の間の接続の数は最大 であることがわかります。j接続された点を接続するすべての直線もLにあり、それぞれが少なくとも接続に寄与します。したがって、このような直線の総数は です。 ${\displaystyle O(n^{2}/2^{3j}+n/2^{j})}$${\displaystyle 2^{j}}$${\displaystyle |L|\cdot {2^{j} \choose 2}\leq {n \choose 2}}$${\displaystyle O(n^{2}/2^{2j}+n)}$${\displaystyle 2^{j}}$${\displaystyle O(n^{2}/2^{3j}+n/2^{j})}$

このような各線は点のペアを接続するため、最大でj接続できる点のペアがわかります。 ${\displaystyle \オメガ (2^{2j})}$${\displaystyle O(n^{2}/2^{j}+2^{j}n)}$

ここで、C を大きな定数とします。等比級数を合計すると、 を満たすあるjに対してj接続された点のペアの数は最大 であることがわかります。 ${\displaystyle C\leq 2^{j}\leq n/C}$${\displaystyle O(n^{2}/C)}$

一方、ペアの総数は です。したがって、 C を十分に大きく選択すると、任意の に対してj接続ではないペア (たとえば) を少なくとも 個見つけることができます。これらのペアを接続する線は、2 個未満のC点を通過するか、 n / C個を超える点を通過します。後者の場合がこれらのペアの 1 つでも当てはまる場合、ベックの定理の最初の結論が得られます。したがって、すべてのペアは2 個未満のC点を通過する線で接続されていると想定できます。ただし、そのような各線は最大で個の点のペアを接続できます。したがって、少なくとも 2 個の点を接続する線が少なくとも 個存在し、 とすることで主張が成り立ちます。 ${\displaystyle {\frac {n(n-1)}{2}}}$${\displaystyle n^{2}/4}$${\displaystyle C\leq 2^{j}\leq n/C}$${\displaystyle n^{2}/4}$${\displaystyle C(2C-1)}$${\displaystyle n^{2}/4C(2C-1)}$${\displaystyle K=4C(2C-1)}$