ハドウィガー予想（組合せ幾何学）

数学における未解決問題

すべての${\displaystyle n}$次元凸体が覆われる$2n$それ自身のより小さなコピー？

数学における未解決問題

組合せ幾何学において、ハドウィガー予想は、n次元ユークリッド空間内の任意の凸体は、元の体と相似な^2n個以下の小さな体で覆うことができ、さらに、 ²ⁿという上限は、その体が平行六面体である場合に限り必要であると述べている。また、その体を照らすのに必要な投光器の数という観点から、これと同等の定式化も存在する。

ハドウィガー予想は、1957年に未解決問題のリストにこの予想を含めたヒューゴ・ハドウィガーにちなんで名付けられました。しかし、この予想はそれ以前にレヴィ（1955年）と、独立にゴーバーグとマルクス（1960年）によって研究されていました。さらに、グラフ彩色に関する別のハドウィガー予想も存在し、一部の文献では、幾何学的ハドウィガー予想はレヴィ・ハドウィガー予想またはハドウィガー・レヴィ被覆問題とも呼ばれています。

2次元の場合はレヴィ（1955）によって解決されたが、3次元の場合でもこの予想は未解決のままである。

正式には、ハドウィガー予想は次のように表されます。Kがn次元ユークリッド空間R ⁿ内の任意の有界凸集合である場合、すべてのs _iが 0 < s _i < 1 の範囲にあり、かつ 2 ^{n 個の}スカラーs _iの集合と 2 ^{n 個}の並進ベクトルv _iの集合が存在する。    

$${\displaystyle K\subseteq \bigcup _{i=1}^{2^{n}}s_{i}K+v_{i}.}$$

さらに、上限はKが平行六面体である場合に限り必要であり、その場合、すべてのスカラー2 ^{nを 1/2 に等しく選択することができます。}

図に示すように、三角形はそれ自身の 3 つの小さなコピーで覆うことができ、より一般的には、任意の次元において単体は、 n / ( n + 1 ) の係数で拡大縮小されたn  +  1 個のコピーで覆うことができます。しかし、正方形を (元の正方形と平行な辺を持つ) より小さな正方形で覆うには、それぞれが大きな正方形の 4 つの角のうち 1 つしか覆うことができないため、4 つの小さな正方形が必要です。高次元では、超立方体、またはより一般的には平行六面体を同じ形状のより小さな相似コピーで覆うには、元の超立方体または平行六面体の各頂点ごとに個別のコピーが必要です。これらの形状は 2 ⁿ個の頂点を持つため、2 ⁿ個のより小さなコピーが必要です。この数は十分でもあります。立方体または平行六面体は、1/2 の係数で拡大縮小された 2 ^{n 個のコピーで覆うことができます。ハドウィガーの予想は、平行六面体がこの問題の最悪のケースであり、他の凸体は 2 n 個}より少ない数のより小さなコピーで覆うことができるというものです。^{[ 1 ]}  

2 次元の場合については、 Levi (1955)によって解決されました。任意の 2 次元の有界凸集合は、それ自身の 4 つの小さなコピーで覆うことができ、4 番目のコピーは平行四辺形の場合にのみ必要です。ただし、いくつかの特殊な場合を除いて、この予想は高次元では未解決のままです。与えられた物体を覆うために必要な小さなコピーの数に関する最もよく知られている漸近上限は^{[ 2 ]です。}$${\displaystyle \displaystyle 4^{n}\exp {\frac {-cn}{\log ^{8}n}},}$$ どこ${\displaystyle c}$は正の定数です。小さい場合、${\displaystyle n}$上限${\displaystyle (n+1)n^{n-1}-(n-1)(n-2)^{n-1}}$Lassak (1988)によって確立された方法は漸近的なものよりも優れている。3 次元では、Papadoperakis (1999)によって16 コピーで常に十分であることが示され、その後Prymak (2023)によって14 コピーで常に十分であることが示されたが、これは 8 コピーという予想された限界からはまだ程遠い。^{[ 1 ]}

この予想は、3次元では中心対称多面体や一定幅の物体など、特定の特殊な凸体に対して成り立つことが知られている。^{[ 1 ]}平行六面体以外の任意のゾノトープを覆うのに必要なコピーの数は最大で${\displaystyle (3/4)2^{n}}$一方、滑らかな表面を持つ物体（つまり、境界点ごとに単一の接平面を持つ物体）の場合、最大で${\displaystyle n+1}$リーヴァイが既に証明したように、体を覆うにはより小さなコピーが必要である。^{[ 1 ]}

• ボルスクの、凸体をより小さな直径の集合で覆うことに関する予想

• ボルトジャンスキー、ウラジミール・G. ;ゴーバーグ、イスラエル( 1985)。「11. ハドウィガー予想」。『組合せ幾何学における結果と問題』。ケンブリッジ：ケンブリッジ大学出版局。44–46頁。ISBN  978-0-521-26923-0。。
• Brass, Peter; Moser, William; Pach, János (2005). "3.3 Levi–Hadwiger被覆問題と照明". Research Problems in Discrete Geometry . Springer-Verlag. pp. 136–142 . ISBN  978-0-387-23815-9。。
• Campos, Marcelo; van Hintum, Peter; Morris, Robert ; Tiba, Marius (2023)、「Bourgain Slicing による Hadwiger 予想に向けて」、International Mathematics Research Notices、2024 (10): 8282–8295、arXiv : 2206.11227、doi : 10.1093/imrn/rnad198。
• Gohberg, Israel Ts. ; Markus, Alexander S. (1960)、「凸集合を相似集合で覆うことに関するある種の問題」、Izvestiya Moldavskogo Filiala Akademii Nauk SSSR (ロシア語)、10 ( 76): 87–90。
• Hadwiger、Hugo (1957)、「Ungelöste Probleme Nr. 20」、Elemente der Mathematik、12 : 121。
• Huang, Han; Slomka, Boaz A.; Tkocz, Tomasz; Vritsiou, Beatrice-Helen (2022)、「薄殻推定によるハドウィガーの被覆問題の改善された境界」、Journal of the European Mathematical Society、24 (4): 1431–1448、arXiv : 1811.12548、doi : 10.4171/jems/1132、ISSN 1435-9855 。
• Lassak, Marek (1988)、「凸集合の境界をタイルで覆う」、アメリカ数学会紀要、104 (1): 269–272、doi : 10.1090/s0002-9939-1988-0958081-7、MR 0958081 。
• パパドペラキス、イオアニス (1999)、「凸体の境界の照明問題の推定${\displaystyle E^{3}}$"、Geometriae Dedicata、75 (3): 275–285、doi : 10.1023/A:1005056207406。
• Prymak, Andriy (2023)、「Hadwigerの被覆問題に対する新しい境界」$\displaystyle \mathbb {E} ^{3}}$SIAM Journal on Discrete Mathematics、37（1）：17–24、doi：10.1137/22M1490314。
• Levi、Friedrich Wilhelm (1955)、「Überdeckung eines Eibereiches durch Parallelverschiebungen seines offenen Kerns」、Archiv der Mathematik、6 (5): 369–370、doi : 10.1007/BF01900507、S2CID 121459171 。