トラクル

トラクルとは、各辺がジョルダン弧で、すべての辺のペアがちょうど一度だけ交わるグラフを平面に埋め込んだものである。辺は共通の端点で交わるか、共通の端点がない場合は内部の点で交わる。後者の場合、交点で交差する必要があり、交差は横断的でなければならない。^[1]

スラックルの特殊なケースである線形スラックルでは、エッジを直線セグメントとして描画するように制限します。任意の点の集合を頂点として線形スラックルを構築する方法の 1 つは、最も遠い点のペアの間にエッジを形成することです。線形スラックルの場合、各接続コンポーネントには最大で 1 つのサイクルが含まれ、このことから、エッジの数は最大で頂点の数と等しくなります。

ジョン・H・コンウェイは、より一般的には、すべてのスラックルには最大で頂点と同じ数の辺があると推測しました。辺の数は最大で頂点の数の定数倍であることが知られています。

線形トラックルは、辺が直線セグメントになるように描かれたトラックルです。ポール・エルデシュが観察したように、すべての線形トラックルの辺の数は、最大で頂点の数と同じです。頂点v が3 つ以上の辺vw、vx、vyに接続されている場合、それらの辺のうち少なくとも 1 つ ( vwとする) は、他の 2 つの辺を分ける線上にあります。この場合、w は次数1 でなければなりません。なぜなら、 vw以外の、wで終わる線分は、 vxとvy の両方に接することができないからです。 wとvw を削除すると、辺と頂点の数の差を変えずに、より小さなトラックルが生成されます。このような削除によって、すべての頂点が最大で 2 つの隣接頂点を持つトラックルになった後、ハンドシェイク補題により、辺の数は最大で頂点の数になります。^[2]エルデシュの証明に基づくと、すべての線形スラックルは擬似フォレストであると推測できます。奇数長のすべてのサイクルは線形スラックルを形成するように配置できますが、偶数長のサイクルではこれは不可能です。これは、サイクルの1つの辺が任意に選択された場合、他のサイクルの頂点は、この辺を通る線の反対側に交互に存在する必要があるためです。

ミカ・パールズは、線形スラックルには最大でn個の辺があることを、線形スラックルではどの辺にも端点があり、その端点における辺の角度は最大で 180° であり、その端点がこの範囲内で最も時計回りの辺であるという事実に基づいて証明しました。そうでなければ、辺の反対側の端点に接続し、辺を通る線の反対側にある 2 つの辺が互いに交差できないことになります。しかし、各頂点は単一の辺に関してのみこの特性を持つことができるため、辺の数は最大で頂点の数に等しくなります。^[3]

エルデシュも観察したように、点集合の直径を実現する点のペアの集合は線状トラクルを形成する必要がある。つまり、2 つの直径が互いに分離することはできない。分離すると、それらの 4 つの端点のペアは、2 つの分離した辺よりも離れた距離にあることになるからである。このため、平面上のn点の集合は、最大でn 個の直径ペアを持つことができ、これは 1934 年にハインツ・ホップとエリカ・パンヴィッツによって提起された疑問に答えている。^[4] アンドリュー・ヴァゾニは、この問題を一般化して、高次元での直径ペアの数の上限を予想した。^[2]

計算幾何学では、回転ノギス法を用いて、凸包に接する平行線を支持する点のペアを接続することにより、凸位置にある任意の点の集合から線形のトラックルを形成することができる。^[5]このグラフには、直径ペアのトラックルがサブグラフとして含まれる。^[6]

ラインハルト多角形の直径は線状トラクルを形成する。線状トラクルの列挙は、直径に対する面積が最大となるn角形を見つけるという最大の小多角形問題を解くのに使用できる。 ^[7]

ジョン・H・コンウェイは、どんなスラックルでも、辺の数は頂点の数と同数以下であると予想した。コンウェイ自身は、辺をパス、頂点をスポットという用語で表現したため、コンウェイのスラックル予想は、もともとは、すべてのスラックルには少なくともパスと同じ数のスポットがあるという形で述べられていた。コンウェイは、この予想を証明または反証する人に1000ドルの賞金を出すと発表し、これはコンウェイの99グラフ問題、ダンザー集合の最小間隔、16手目以降のシルバー貨幣の獲得者などを含む一連の懸賞問題の一部であった。 ^[8]

同様に、スラックル予想は、すべてのスラックルは擬似森林であると述べることができる。より具体的には、スラックル予想が正しい場合、スラックルはウッドオールの結果によって正確に特徴付けられる。すなわち、長さ4のサイクルがなく、最大で1つの奇数サイクルしかない擬似森林である。^{[1] [9]}

C ₄以外のすべてのサイクル グラフには、スラックル埋め込みがあることが証明されており、これは予想が正確であることを示しています。つまり、パスと同じ数のスポットを持つスラックルが存在します。反対に、最悪のシナリオでは、スポットの数がパスの数の 2 倍になりますが、これも実現可能です。

スラックル予想は、すべての辺がx単調曲線であり、すべての垂直線が最大で1回交差するように描かれたスラックルに対して真であることが知られています。 ^[3]

Lovász、Pach、Szegedy (1997) は、すべての二部トラクルは平面グラフであるが、平面的に描かれていないことを証明した。^[1]結果として、彼らは、n頂点を持つすべてのトラクル可能グラフは最大で 2 n  − 3 の辺を持つことを示しています。それ以来、この境界は数回改良されてきました。最初は 3( n  − 1)/2 に改良され、^[10]別の改良により、およそ 1.428 nの境界がもたらされました。^{[11]さらに、後者の結果を証明するために使用される方法は、任意の ε > 0 に対して、境界を (1 + ε)} nに改良するか、予想を反証する有限アルゴリズムをもたらします。現在の記録は、1.393 nの境界を証明した Xu (2021) によるものです。^[12]

もしこの予想が偽ならば、最小の反例は頂点を共有する2つの偶数サイクルの形をとるだろう。^[9]したがって、この予想を証明するには、このタイプのグラフがトラクルとして描くことができないことを証明すれば十分であろう。

• thrackle.org - 問題に関するウェブサイト