Hirschova domněnka - Hirsch conjecture - Wikipedia

Graf an Icosidodecahedron, příklad, pro který je domněnka pravdivá.

v matematické programování a polyedrická kombinatorika, Hirschova domněnka je prohlášení, že okraj -vrchol graf z n-aspekt polytop v d-dimenzionální Euklidovský prostor má průměr ne více než n − d. To znamená, dva vrcholy polytopu musí být navzájem spojeny cestou délka nejvíce n − d. Domněnka byla poprvé uvedena v dopise od Warren M. Hirsch ^{[es ]} na George B. Dantzig v roce 1957^[1][2] a byl motivován analýzou simplexní metoda v lineární programování, protože průměr mnohostěnu poskytuje dolní mez počtu kroků potřebných pro simplexní metodu. Je nyní známo, že domněnka je obecně nepravdivá.

Hirschova domněnka byla prokázána pro d <4 a pro různé speciální případy,^[3] zatímco nejznámější horní hranice průměru jsou pouze subexponenciální n a d.^[4] Po více než padesáti letech byl v květnu 2010 oznámen protiklad Francisco Santos Leal, od University of Cantabria.^[5][6][7] Výsledek byl představen na konferenci 100 let v Seattlu: matematika Klee a Grünbaum a objevil se v Annals of Mathematics.^[8] Příspěvek konkrétně představil 43dimenzionální polytop 86 fazet o průměru větším než 43. Protiklad nemá žádné přímé důsledky pro analýzu simplexní metody, protože nevylučuje možnost větší, ale stále lineární nebo polynomický počet kroků.

Byly uvedeny různé ekvivalentní formulace problému, například d-kroková domněnka, která uvádí, že průměr libovolné 2d-facetový polytop v d-dimenzionální euklidovský prostor není větší než d; Santos Lealův protiklad také vyvrací tuto domněnku.^[1][9]

Prohlášení o domněnce

The graf konvexní polytop ${ displaystyle P}$ je jakýkoli graf jehož vrcholy jsou v bijekce s vrcholy ${ displaystyle P}$ takovým způsobem, že libovolné dva vrcholy grafu jsou spojeny hranou právě tehdy, pokud jsou dva odpovídající vrcholy ${ displaystyle P}$ jsou spojeny hranou mnohostěnu. The průměr z ${ displaystyle P}$, označeno ${ displaystyle delta (P)}$, je průměr kteréhokoli z jeho grafů. Tyto definice jsou dobře definované protože jakékoli dva grafy stejného polytopu musí být izomorfní jako grafy. Můžeme pak vyslovit Hirschovu domněnku takto:

Dohad Nechat ${ displaystyle P}$ být d-rozměrný konvexní polytop s n fazety. Pak ${ displaystyle delta (P) leq n-d}$.

Například krychle ve třech rozměrech má šest fazet. Hirschova domněnka pak naznačuje, že průměr této krychle nemůže být větší než tři. Přijetí domněnky by znamenalo, že jakékoli dva vrcholy krychle mohou být spojeny a cesta od vrcholu k vrcholu pomocí maximálně tří kroků. Pro všechny polytopy dimenze alespoň 8 je tato vazba ve skutečnosti optimální; žádný polytop kóty ${ displaystyle d geq 8}$ má průměr menší než n-d, s n je počet jejích aspektů, jako dříve.^[10] Jinými slovy, pro téměř všechny případy poskytuje domněnka minimální počet kroků potřebných ke spojení libovolných dvou vrcholů mnohostěn cestou podél jeho okrajů. Protože simplexní metoda v podstatě funguje konstrukcí cesty z nějakého vrcholu proveditelný region do optimálního bodu by Hirschova domněnka poskytla spodní hranici potřebnou pro ukončení simplexové metody v nejhorším případě.

Hirschova domněnka je zvláštním případem polynomiální Hirschova domněnka, který tvrdí, že existuje nějaké kladné celé číslo k takové, že pro všechny polytopy ${ displaystyle P}$, ${ displaystyle delta (P) = O (n ^ {k})}$, kde n je počet aspektů P.

Pokrok a průběžné výsledky

Hirschova domněnka se prokázala jako pravdivá pro řadu případů. Například jakýkoli mnohostěn s dimenzí 3 nebo nižší splňuje domněnku. Žádný d-dimenzionální polytop s n aspekty takové ${ displaystyle n-d leq 6}$ uspokojuje také domněnku.^[11]

Další pokusy o vyřešení domněnky se projevily z touhy formulovat jiný problém, jehož řešení by znamenalo Hirschovu domněnku. Jedním z příkladů zvláštního významu je domněnka o d-kroku, relaxace Hirschova domněnky, která se ve skutečnosti prokázala jako rovnocenná.

Teorém Následující prohlášení jsou ekvivalentní:

1. ${ displaystyle delta (P) leq n-d}$ pro všechny d-rozměrné polytopy ${ displaystyle P}$ s n fazety.
2. ${ displaystyle delta (P) leq d}$ pro všechny d-rozměrné polytopy ${ displaystyle P}$ s 2d fazety.

Jinými slovy, k prokázání nebo vyvrácení Hirschovy domněnky stačí vzít v úvahu polytopy s přesně dvakrát větším počtem aspektů, než je jejich rozměr. Další významnou relaxací je, že Hirschova domněnka platí pro všechny polytopy právě tehdy, pokud platí pro všechny jednoduché polytopy.^[12]

Protiklad

The osmistěn je jedním z nejznámějších příkladů vřetena.

Bohužel Hirschova domněnka není ve všech případech pravdivá, jak ukázal Francisco Santos v roce 2011. Santosova explicitní konstrukce protipříkladu vychází jednak ze skutečnosti, že domněnku lze uvolnit, aby zvážila pouze jednoduché polytopy, jednak z ekvivalence mezi Hirschem a d- krok domněnky.^[13] Zejména Santos vytváří svůj protiklad zkoumáním konkrétní třídy tzv. Polytopů vřetena.

Definice A d-vřeteno je a d-dimenzionální polytop ${ displaystyle P}$ pro které existuje dvojice odlišných vrcholů, takže každý aspekt ${ displaystyle P}$ obsahuje přesně jeden z těchto dvou vrcholů.

Délka nejkratší cesty mezi těmito dvěma vrcholy se nazývá délka vřetena. Vyvrácení Hirschova domněnky se opírá o následující větu označovanou jako silná věta o d-kroku pro vřetena.

Věta (Santos) Nechat ${ displaystyle P}$ být d-vřeteno. Nechat n být počet jeho aspektů, a nechť l být jeho délka. Pak existuje ${ displaystyle (n-d)}$-vřeteno, ${ displaystyle P '}$, s ${ displaystyle 2n-2d}$ fazety a délka ohraničená níže ${ displaystyle l + n-2d}$. Zejména pokud ${ displaystyle l> d}$, pak ${ displaystyle P '}$ porušuje d- krok domněnka.

Santos poté pokračuje v konstrukci 5-dimenzionálního vřetena o délce 6, což dokazuje, že existuje další vřeteno, které slouží jako protipříklad Hirschova domněnky. První z těchto dvou vřeten má 48 fazet a 322 vrcholů, zatímco vřeteno, které ve skutečnosti vyvrací domněnku, má 86 fazet a je 43-rozměrné. Tento protiklad nevyvrací polynomiální Hirschovu domněnku, která zůstává otevřeným problémem.^[14]

Poznámky

Reference

• Dantzig, George B. (1963), Lineární programování a rozšíření, Princeton Univ. lis. Přetištěno v sérii Princetonské mezníky v matematice, Princeton University Press, 1998.
• Kalai, Gil (10. května 2010). „Francisco Santos vyvrací Hirschovu domněnku“. Citováno 11. května 2010.CS1 maint: ref = harv (odkaz)
• Kalai, Gil; Kleitman, Daniel J. (1992), „Quasi-polynomial bound for the diameter of graphs of polyhedra“, Bulletin of the American Mathematical Society, 26 (2): 315–316, arXiv:matematika / 9204233, doi:10.1090 / S0273-0979-1992-00285-9, PAN  1130448.
• Klee, Victor; Walkup, David W. (1967), „The d-kroková domněnka mnohostěnů dimenze d < 6", Acta Mathematica, 133: 53–78, doi:10.1007 / BF02395040, PAN  0206823.
• Miranda, Eva (2012), „Hirschova domněnka byla vyvrácena: Rozhovor s Franciscem Santosem“ (PDF), Zpravodaj Evropské matematické společnosti (86): 31–36.
• Naddef, Denis (1989), „Hirschova domněnka platí pro (0,1) -polytopes“, Matematické programování, 45 (1): 109–110, doi:10.1007 / BF01589099, PAN  1017214.
• Santos, Francisco (2011), „Protiklad k Hirschově domněnce“, Annals of Mathematics, Princeton University a Institute for Advanced Study, 176 (1): 383–412, arXiv:1006.2814, doi:10.4007 / annals.2012.176.1.7, PAN  2925387
• Ziegler, Günter M. (1994), „Hirschova domněnka“, Přednášky na Polytopech, Postgraduální texty z matematiky, 152, Springer-Verlag, str. 83–93.