ビッグライン・ビッグクリーク予想

大線大クリーク予想は、離散幾何学における未解決の問題であり、ユークリッド平面上の多数の点の有限集合には、多数の共線上の点が存在するか、多数の点が相互に見える（3 番目の点が 2 つの点を遮って互いが見えなくなる）という予想である。

より正確には、ビッグライン・ビッグクリーク予想は、任意の正の整数 と に対して、任意の点の集合に同一線上の点（「ビッグライン」）、相互に見える点（「ビッグクリーク」）、またはその両方が含まれるような別の数 が存在するはずであると述べています。^{[1] [2]}${\displaystyle k}$${\displaystyle \ell}$${\displaystyle n_{k,\ell}}$${\displaystyle n_{k,\ell}}$${\displaystyle \ell}$${\displaystyle k}$

ビッグラインビッグクリーク予想は、Jan Kára、Attila Pór、David R. Woodによって2005年の出版物で提唱されました。^{[1] [2]}これにより、点集合における点間の可視性に関する多くの追加研究が行われました。^[3]

一般位置（同一直線上にない3点）の有限点集合は必ず大きなクリークを含むため、 に対してこの予想は成り立ちます。さらに、相互に見える5点を持たない有限点集合（整数格子と凸集合の交差点など）は必ず多くの同一直線上の点を含むため、 に対してこの予想は成り立ちます。^[4]${\displaystyle \ell \leq 3}$${\displaystyle k\leq 5}$

整数格子の例を一般化すると、一般的な線形投影を使用して、サイズの格子点の次元システムを 平面に投影すると、共線上の点や相互に見える点がない点の集合が生成されます。したがって、が存在する場合、それは より大きくなければなりません。^[2]${\displaystyle d}$${\displaystyle (\ell -1)\times (\ell -1)\times \cdots =(\ell -1)^{d}}$${\displaystyle \ell}$${\displaystyle 2^{d}+1}$${\displaystyle n_{k,\ell}}$${\displaystyle (\ell -1)^{\log _{2}(k-1)}}$

任意の点のシステム間の可視性は、点の可視性グラフを使用して分析できます。可視性グラフは、点を頂点とし、2 つの点を結ぶ線分が他の点と交わっていない場合は常に、2 つの点を辺で結ぶグラフです。ビッグ ライン ビッグ クリーク予想の「ビッグ クリーク」は、可視性グラフ内のクリークです。ただし、完全に共線的な点のシステムは、2 部可視性グラフを持つことで特徴付けることができますが、この特徴付けは点のサブセットには適用されません。サブセットは、共線的でなくても、可視性グラフの 2 部誘導サブグラフを持つことができます。^[2]

ハッピーエンド問題の解決法によれば、一直線に3つ並んでいない点の集合には、凸多角形の頂点を形成する大きな集合が含まれる。より一般的には、同じ方法を使用して、十分な数の点の集合には、共線上の点または凸位置にある点のいずれかが含まれることが証明できる。ただし、これらの凸点のペアの中には、それらが形成する凸多角形内の点によって見えなくなるものがある。^[2]${\displaystyle \ell}$${\displaystyle k}$

関連するもう 1 つの質問は、一般位置 (または指定された数を超える点の線がない位置) の点に、空の凸多角形または穴の頂点が含まれているかどうかです。これは、頂点が点集合に属しているが、点集合とその凸包の交差内に他の点がない多角形です。指定されたサイズの穴が存在する場合、その頂点はすべて必ず互いに見えます。一般位置にある十分に大きい点の集合はすべて、空の五角形[ ^4]または六角形^{[5] [6]}を形成する 5 つの頂点を含みますが、空の七角形を持たない、任意の大きさの集合が一般位置に存在します。^[7]

大直線大クリーク予想の強化版では、大クリークが「可視島」、つまり相互に可視で、与えられたより大きな点集合を凸集合と交差させることで形成される点の集合であることが求められます。しかし、この強化版は誤りです。一般的な位置にある点集合に空の七角形がない場合、その各点を密接した共線点の 3 つに置き換えると、一直線上に 4 つがなく、13 点以上の可視島がない点集合が生成されます。^[8]

同じ予想の無限バージョンはあり得ない。PórとWoodは、直線上に4つの点がなく、相互に見える点の三角形がない可算な点集合の例を見つけた。^[9]