ヒルシュ予想

数理計画法と多面体組合せ論において、ヒルシュ予想とは、 d 次元ユークリッド空間の n 面体多面体の辺頂点グラフの直径はn − d以下であるという主張である 。つまり 、 多面体の任意の2 つの頂点は、長さがn  −  d以下のパスによって互いに接続されていなければならない。この予想は、 1957 年にウォーレン・M・ヒルシュ ^[es]がジョージ・B・ダンツィヒに宛てた手紙^{[1] [2]で初めて提唱され、}線型計画法における単体法の解析がきっかけとなった。これは、多面体の直径が単体法に必要なステップ数の下限値を提供するためである。この予想は現在では一般に誤りであることがわかっている。

ヒルシュ予想はd < 4 およびさまざまな特殊なケースに対して証明されましたが^[3]、直径に関する最もよく知られている上限はnとdに関してのみ指数関数的です。^{[4] 50年以上経った2010年5月、}カンタブリア大学のFrancisco Santos Lealによって反例が発表されました。^{[5] [6] [7]この結果は、シアトルでの100年：}クレーとグリューンバウムの数学という会議で発表され、Annals of Mathematicsに掲載されました。^[8]具体的には、論文では、直径が43を超える 86 面を持つ 43 次元の多面体が提示されました。 この反例は、より大きなステップ数でも線形または多項式数である可能性を排除しないため、単体法の分析に直接的な影響はありません。

この問題には、 d次元ユークリッド空間内の任意の2d面多面体の直径はd以下であるというdステップ予想など、さまざまな同等の定式化が提示されている。サントス・レアルの反例もこの予想を反証している。^{[1] [9]}

凸多面体のグラフとは、その頂点が の頂点と一対一であるグラフのことです。 の対応する 2 つの頂点が多面体の辺で結ばれている場合のみ、グラフの任意の 2 つの頂点が辺で結ばれます。の直径はと表記され、そのグラフのいずれか 1 つの直径です。これらの定義は明確に定義されています。同じ多面体の任意の 2 つのグラフはグラフとして同型でなければならないからです。したがって、ヒルシュ予想は次のように述べられます。 ${\displaystyle P}$${\displaystyle P}$${\displaystyle P}$${\displaystyle P}$${\displaystyle \delta (P)}$

予想 をn面を持つd次元凸多面体とします。このとき。 ${\displaystyle P}$${\displaystyle \delta (P)\leq nd}$

たとえば、3次元の立方体には6つの面があります。ヒルシュ予想は、この立方体の直径は3より大きくできないことを示しています。予想を受け入れると、立方体の任意の2つの頂点は、最大3つのステップを使用して、頂点から頂点へのパスによって接続される可能性があります。少なくとも8次元のすべての多面体に対して、この境界は実際に最適です。次元の多面体の直径はnd未満ではありません。nは前述のように、その面の数です。^[10]言い換えると、ほぼすべての場合、予想は多面体の任意の2つの頂点をその辺に沿ったパスで接続するために必要な最小ステップ数を提供します。単体法は基本的に、実行可能領域のいくつかの頂点から最適なポイントへのパスを構築することによって機能するため、ヒルシュ予想は、単体法が最悪のシナリオで終了するために必要な下限を提供します。 ${\displaystyle d\geq 8}$

ヒルシュ予想は、多項式ヒルシュ予想の特殊なケースであり、すべての多面体 に対して、となる正の整数k が存在するというものです。ここで、n はPの面の数です。 ${\displaystyle P}$${\displaystyle \delta (P)=O(n^{k})}$

ヒルシュ予想は多くのケースで正しいことが証明されている。例えば、次元が3以下の多面体は予想を満たす。また、 n面を持つd次元多面体も予想を満たす。^[10]${\displaystyle nd\leq 6}$

この予想を解こうとする他の試みは、その解決がヒルシュ予想を示唆する別の問題を定式化したいという願望から生まれた。特に重要な例の 1 つは、ヒルシュ予想を緩和したd ステップ予想であり、実際にヒルシュ予想と同等であることが証明されている。

定理次のステートメントは同等です。

1. ${\displaystyle \delta (P)\leq nd}$n面を持つすべてのd次元多面体に対して。${\displaystyle P}$
2. ${\displaystyle \delta (P)\leq d}$2Dファセットを持つすべてのd次元多面体に対して。${\displaystyle P}$

言い換えれば、ヒルシュ予想を証明または反証するためには、次元のちょうど2倍の面を持つ多面体だけを考えればよい。もう一つの重要な緩和点は、ヒルシュ予想がすべての多面体に対して成立するためには、すべての単純多面体に対して成立する必要があるということである。^[10]

残念ながら、2011年にフランシスコ・サントスが示したように、ヒルシュ予想はすべてのケースで当てはまるわけではありません。サントスが明示的に反例を構築したのは、予想を緩和して単純な多面体のみを考慮することができるという事実と、ヒルシュ予想とdステップ予想が同等であることの両方から来ています。^{[8]特に、サントスは}スピンドルと呼ばれる特定の種類の多面体を調べることで反例を生み出しています。

定義dスピンドルとは、 d次元多面体であり、その多面体には 2 つの異なる頂点のペアが存在し、 のすべての面にはこれらの 2 つの頂点のうちの 1 つだけが含まれます。 ${\displaystyle P}$${\displaystyle P}$

これら 2 つの頂点間の最短経路の長さは、スピンドルの長さと呼ばれます。ヒルシュ予想の反証は、スピンドルの強い d ステップ定理と呼ばれる次の定理に基づいています。

定理 (サントス) をdスピンドルとします。nをその面の数、l を長さとします。すると、面を持ち、長さが 未満に制限される-スピンドルが存在します。特に、 の場合、 はdステップ予想に違反します。 ${\displaystyle P}$${\displaystyle (nd)}$${\displaystyle P'}$${\displaystyle 2n-2d}$${\displaystyle l+n-2d}$${\displaystyle l>d}$${\displaystyle P'}$

サントスは次に長さ6の5次元スピンドルを構築し、ヒルシュ予想の反例となる別のスピンドルが存在することを証明した。この2つのスピンドルの最初のスピンドルは48面と322頂点を持ち、予想を実際に反証するスピンドルは86面と43次元である。この反例は多項式ヒルシュ予想を反証するものではなく、未解決の問題のままである。^[8]

• ダンツィグ、ジョージ B. (1963)、線形計画法と拡張、プリンストン大学出版局プリンストン大学出版局の「プリンストン数学ランドマークシリーズ」に1998年に再版。
• Kalai, Gil (2010 年 5 月 10 日)。「Francisco Santos が Hirsch 予想を反証」 。2010年5 月 11 日閲覧。
• カライ、ギル;クライトマン、ダニエル J. (1992)、「多面体グラフの直径に対する準多項式境界」、アメリカ数学会誌、26 (2): 315–316、arXiv : math/9204233、doi :10.1090/S0273-0979-1992-00285-9、MR  1130448、S2CID  37821778。
• クレー、ビクター、ウォークアップ、デイビッド W. (1967)、「次元d < 6の多面体に対するdステップ予想 」、Acta Mathematica、133 : 53–78、doi : 10.1007/BF02395040、MR  0206823。
• ミランダ、エヴァ（2012）、「ヒルシュ予想は反証された：フランシスコ・サントスとのインタビュー」（PDF）、ヨーロッパ数学会ニュースレター（86）：31–36。
• Naddef, Denis (1989)、「Hirsch 予想は (0,1)-多面体に対して真である」、数学プログラミング、45 (1): 109–110、doi :10.1007/BF01589099、MR  1017214、S2CID  24632864。
• サントス、フランシスコ(2011)、「ヒルシュ予想に対する反例」、数学年報、176 (1)、プリンストン大学高等研究所: 383–412、arXiv : 1006.2814、doi :10.4007/annals.2012.176.1.7、MR  2925387、S2CID  15325169
• ジーグラー、ギュンター・M. (1994)、「ヒルシュ予想」、多面体に関する講義、数学の大学院テキスト、第 152 巻、シュプリンガー出版、pp. 83–93。