三脚パッキング

組合せ論において、三脚パッキングは、3次元グリッド内の多数の互いに素な三脚を見つける問題である。三脚とは、頂点を共有する3つの正の軸に沿った光線に沿ったグリッドキューブの和集合である無限ポリキューブである。^[1]

三脚や関連図形をタイリングおよびパッキングするいくつかの問題が、1967 年にSherman K. Steinによって定式化されました。^[2] Stein は当初、この問題の三脚を「セミクロセス」と呼び、Solomon W. GolombはこれをStein コーナーとも呼びました。^[3]互いに素な三脚のコレクションは、単調行列としてコンパクトに表現できます。単調行列は、各行と各列に沿って非ゼロのエントリが増加し、等しい非ゼロのエントリが単調なセルのシーケンスに配置される正方行列です。^[4]また、この問題は、「2 比較可能性」と呼ばれる互換性条件を満たす 3 つのセットを見つける、または凸多角形内の互換性のある三角形のセットを見つけるという観点から定式化することもできます。^[1]

頂点をグリッド内に詰め込むことができる三脚の数の最良の下限は であり、最良の上限は であり、どちらも大きなオメガ記法で表されます。^{[1] [5]}${\displaystyle n\times n\times n}$${\displaystyle \オメガ (n^{1.546})}$${\displaystyle n^{2}/\exp \Omega (\log ^{*}n)}$

三脚問題の解の頂点の座標は、 2比較可能な3つの組の集合を形成します。2つの3つ組は、少なくとも2つの座標で一方の3つ組が他方の3つ組より小さいか、少なくとも2つの座標で一方の3つ組が他方の3つ組より大きい場合、2比較可能であると定義されます。この条件により、これらの3つ組から定義された三脚には交差する光線がないことを保証します。^[1]${\displaystyle (x_{i},y_{i},z_{i})}$

この問題のもう 1 つの同等の 2 次元バージョンは、正方形のセルの配列 (インデックスは から ) のセルの何個に からまでの数字を入力できるかを尋ねます。この場合、配列の各行と各列の空でないセルは厳密に増加する数列を形成し、各値を保持する位置は配列内で単調な連鎖を形成します。これらの特性を持つ配列は単調行列と呼ばれます。頂点を持つ互いに素な三脚のコレクションは、配列セルに数字を配置することで単調行列に変換でき、その逆も可能です。^[1]${\displaystyle n\times n}$${\displaystyle 1}$${\displaystyle n}$${\displaystyle 1}$${\displaystyle n}$${\displaystyle i}$${\displaystyle (x_{i},y_{i},z_{i})}$${\displaystyle z_{i}}$${\displaystyle (x_{i},y_{i})}$

この問題は、凸多角形の頂点間で、頂点を共有する2つの三角形がその頂点で入れ子の角度を持たないように、できるだけ多くの三角形を見つける問題と同等です。この三角形を数える問題はピーター・ブラス^{[6]によって提起され、三脚パッキングとの同等性はアロノフら[1]}によって観察されました。

三脚を用いた三脚パッキング問題の解法は簡単に見つけられる。^[1]例えば、 の場合、三つ組 は2比較可能である。 ${\displaystyle \Omega (n^{3/2})}$${\displaystyle k=\lfloor {\sqrt {n}}\rfloor }$${\displaystyle \Omega (n^{3/2})}$$${\displaystyle {\bigl \{}(ak+b+1,bk+c+1,ak+c+1){\big |}a,b,c\in [0,k-1]{\bigr \}}}$$

この素朴な境界にいくつかの改良を加えた後、^{[7] [8] [9]}ガワーズとロングは、濃度の三脚問題の解決策を見つけました。^[5]${\displaystyle \Omega (n^{1.546})}$

三脚パッキング問題の任意の解から、 から までの数字の 3 つのコピー (3 つの座標のそれぞれに 1 つ) を頂点とし、各三脚の頂点の座標に対応する 3 つの頂点を結ぶ辺の三角形を持つバランスの取れた 3 部グラフを導出できます。これらのグラフには他の三角形は存在しません (これらは局所線型グラフ)。他の三角形があると 2 比較可能性の違反につながるためです。したがって、Ruzsa–Szemerédi 問題(この問題の 1 つのバージョンは、バランスの取れた 3 部局所線型グラフの最大辺密度を見つけることです) の既知の上限により、グリッドに詰め込むことができる互いに素な三脚の最大数はであり、より正確にはです。^{[1] [5] [9] [10]}ティスキンは「パラメータのより厳密な分析」により、多重対数因子による2乗未満の境界を生成できると書いているが、^[9]彼は詳細を示しておらず、その数がであることを証明するためにルザ・セメレディ問題で知られているのと同じ技術しか使用していないため、このより強い主張は間違いであると思われる。^[1]${\displaystyle 0}$${\displaystyle n-1}$${\displaystyle n\times n\times n}$${\displaystyle o(n^{2})}$${\displaystyle n^{2}/\exp \Omega (\log ^{*}n)}$${\displaystyle o(n^{2})}$

ディーン・ヒッカーソンの議論によれば、三脚は一定密度の空間を詰め込むことができないため、高次元の類似の問題でも同じことが言える。^[4]

三脚問題の小さな例については、正確な解が知られています。立方体に詰め込むことができる三脚の数は、次のとおりです。^{[9] [11] [12] [13]}${\displaystyle n\times n\times n}$${\displaystyle n\leq 11}$

たとえば、図は立方体に収納できる 11 個の三脚を示しています。 ${\displaystyle 5\times 5\times 5}$

の異なる単調行列の数は^[14]である。${\displaystyle n}$${\displaystyle n=1,2,3,\dots }$