三脚パッキング
数学における未解決問題
与えられた立方体の中に頂点を詰め込むことができる三脚はいくつありますか?
数学におけるさらなる未解決問題
三脚パッキングとそれに対応する単調行列。この例は、2次元比較可能な集合{(1,1,1), (1,3,3), (2,1,2), (2,4,3), (3,1,4), (3,4,5), (4,2,1), (4,5,3), (5,2,2), (5,3,4), (5,5,5)}に対応する。[1]

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

三脚および関連図形のタイリングとパッキングに関するいくつかの問題は、1967年にシャーマン・K・スタインによって定式化されました。[2]スタインは当初、この問題の三脚を「セミクロセス」と呼び、ソロモン・W・ゴロムはスタインコーナーとも呼びました。[3]互いに素な三脚の集合は、単調行列として簡潔に表現できます。単調行列とは、各行と各列に沿って非ゼロの要素が増加し、等しい非ゼロの要素が単調なセルの列に配置される正方行列です。[4]また、この問題は、「2-比較可能性」と呼ばれる適合条件を満たす3つの要素の集合、または凸多角形内の適合する三角形の集合を見つける問題として定式化することもできます。[1]

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

同等の問題

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

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

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

下限

三脚パッキング問題の解は三脚を用いて簡単に見つけることができる。 の場合、三脚 は 2比較可能である。[1]例えば、との場合、この構成により以下の要素を持つ単調行列が生成される。 Ω ( n 3 / 2 ) {\displaystyle \Omega (n^{3/2})} k = ⌊ n ⌋ {\displaystyle k=\lfloor {\sqrt {n}}\rfloor } Ω ( n 3 / 2 ) {\displaystyle \Omega (n^{3/2})} { ( a k + b + 1 , b k + c + 1 , a k + c + 1 ) | a , b , c ∈ [ 0 , k − 1 ] } {\displaystyle {\bigl \{}(ak+b+1,bk+c+1,ak+c+1)\mathrel {\big |} a,b,c\in [0,k-1]{\bigr \}}} n = 9 {\displaystyle n=9} k = 3 {\displaystyle k=3} 9 × 9 {\displaystyle 9\times 9} 27 {\displaystyle 27} ( 7 8 9 7 8 9 7 8 9 4 5 6 4 5 6 4 5 6 1 2 3 1 2 3 1 2 3 ) {\displaystyle {\begin{pmatrix}&&&&&&7&8&9\\&&&7&8&9&&&\\7&8&9&&&&&&\\&&&&&&4&5&6\\&&&4&5&6&&&\\4&5&6&&&&&&\\&&&&&&1&2&3\\&&&1&2&3&&&\\1&2&3&&&&&&\\\end{pmatrix}}}

この単純な境界にいくつかの改良を加えた後、[7] [8] [9] Gowers と Long は、濃度 の三脚問題に対する解法を発見しました。彼らが観察しているように、問題のサイズに対して三脚の数が多い任意の三脚パッキングは、行列のクロネッカー積に似た再帰的構成により、指数が より大きい解の族に拡張できます。しかし、彼らの探索では、この再帰的構成を開始するための適切な三脚パッキングは見つかりませんでした。その代わりに、彼らは、 2 つの比較可能な直方体をより大きな直方体の中に詰め込むという問題の幾何学的緩和を定式化し、直方体が整数ではなく実数の座標を持つことができるようにしました。彼らは、三脚問題に対する5つの三脚解を表す単位直方体から歪んだ5つの直方体を発見した。これらの直方体を同じ5つの直方体のコピーに再帰的に展開すると、幾何学問題の解が得られ、これは濃度 の三脚パッキングに再変換できる。この解の指数は数値的に次のように計算された。ここで は[5]を満たす最大の実数である。 Ω ( n 1.546 ) {\displaystyle \Omega (n^{1.546})} n 1.5 {\displaystyle n^{1.5}} n {\displaystyle n} 1.5 {\displaystyle 1.5} n = 3 {\displaystyle n=3} Ω ( n 1.546 ) {\displaystyle \Omega (n^{1.546})} 3 α {\displaystyle 3\alpha } α {\displaystyle \alpha } 1 ≤ sup 0 < x < 1 2 2 x 3 α + 3 x 2 α ( 1 − 2 x ) α . {\displaystyle 1\leq \sup _{0<x<{\tfrac {1}{2}}}2x^{3\alpha }+3x^{2\alpha }(1-2x)^{\alpha }.}

上限

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

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

小さなインスタンス

三脚問題の小さな例については、厳密な解が知られています。立方体に詰め込める三脚の数は、 の場合、以下の通りです: [9] [11] [12] [13] n × n × n {\displaystyle n\times n\times n} n ≤ 11 {\displaystyle n\leq 11}

1、2、5、8、11、14、19、23、28、32、38、...

たとえば、図は立方体に詰め込める 11 個の三脚を示しています。 5 × 5 × 5 {\displaystyle 5\times 5\times 5}

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

2、19、712、87685、31102080、28757840751、...

参考文献

  1. ^ abcdefghij アロノフ、ボリス; Dujmović, ヴィダ;パット・モーリン;おっと、オーレリアン。 Schultz Xavier da Silveira、Luís Fernando (2019)、「凸点集合内の三角形に対するトゥラン型定理の詳細」、Electronic Journal of Combinatorics、26 (1): P1.8、doi : 10.37236/7224
  2. ^ スタイン、SK（1967）、「部分集合による因数分解」、パシフィック・ジャーナル・オブ・マスマティクス、22（3）：523–541、doi：10.2140/pjm.1967.22.523、MR  0219435
  3. ^ Golomb, SW (1969)、「誤差測定基準の一般的な定式化」、IEEE Transactions on Information Theory、IT-15: 425– 426、doi :10.1109/tit.1969.1054308、MR  0243902
  4. ^ ab Stein, Sherman K. ; Szabó, Sándor (1994), Algebra and Tiling: Homomorphisms in the Service of Geometry , Carus Mathematical Monographs, vol. 25, Washington, DC: Mathematical Association of America, p. 97, ISBN 0-88385-028-1、MR  1311249
  5. ^ abc Gowers, WT ; Long, J. (2021年1月)、「-増加シーケンスの-タプルの長さ」、Combinatorics, Probability and Computing、30 (5): 686– 721、arXiv : 1609.08688、doi :10.1017/s0963548320000371 s {\displaystyle s} r {\displaystyle r}
  6. ^ Braß, Peter (2004), 「Turán型極値問題（凸幾何学的ハイパーグラフ用）」, Pach, János (編), 『幾何学的グラフの理論に向けて』 , Contemporary Mathematics, vol. 342, Providence, Rhode Island: American Mathematical Society, pp.  25– 33, doi :10.1090/conm/342/06128, ISBN 978-0-8218-3484-8、MR  2065250
  7. ^ ウィリアム・ハマカー、シャーマン・スタイン（1984年）「特定の誤差球による組み合わせパッキング」IEEE Transactions on Information Theory、30（2、パート2）：364–368、doi：10.1109/TIT.1984.1056868、MR  0754867 R 3 {\displaystyle \mathbf {R} ^{3}}
  8. ^ スタイン、シャーマン・K.（1995年3月）「三脚の梱包」、数学エンターテイメント、数学インテリジェンサー、17（2）：37-39、doi：10.1007/bf03024896ゲイル、デイヴィッド（1998年）、ゲイル、デイヴィッド（編）、トラッキング・ザ・オートマチック・アント、シュプリンガー・フェアラーク、pp.  131– 136、doi :10.1007/978-1-4612-2192-0、ISBNに転載 0-387-98272-8、MR  1661863
  9. ^ abcd Tiskin, Alexander (2007)、「三脚のパッキング：密度ギャップの縮小」、離散数学、307 (16): 1973– 1981、doi : 10.1016/j.disc.2004.12.028、MR  2326159
  10. ^ Loh、Po-Shen (2015)、指示されたパス: Ramsey から Ruzsa およ​​び Szemerédi まで、arXiv : 1505.07312
  11. ^ Szabó、Sándor (2013)、「グラフ内の単調行列とクリーク検索」、Ann.大学科学。ブダペスト支部計算します。、41 : 307–322、土井:10.1080/00455091.2001.10717569、MR  3129145
  12. ^ エステルガルド、パトリック RJ; Pöllänen、Antti (2019)、「三脚パッキンに関する新しい結果」(PDF)、離散幾何学および計算幾何学、61 (2): 271–284、doi :10.1007/s00454-018-0012-2、MR  3903789
  13. ^ Sloane, N. J. A. (編)、「シーケンス A070214」、整数シーケンスのオンライン百科事典、OEIS Foundation
  14. ^ Sloane, N. J. A. (編)、「シーケンス A086976」、整数シーケンスのオンライン百科事典、OEIS Foundation
Retrieved from "https://en.wikipedia.org/w/index.php?title=Tripod_packing&oldid=1308936834"