Hirsch gissning

Grafen för en Icosidodecahedron , ett exempel för vilket gissningarna är sanna.

Inom matematisk programmering och polyedrisk kombinatorik är Hirsch -förmodan påståendet att kant - vertex - grafen för en n - fasettpolytop i d - dimensionell euklidisk rymd har en diameter som inte är mer än n - d . Det vill säga att alla två hörn av polytopen måste vara anslutna till varandra med en längdväg som högst n − d . Gissningen framfördes först i ett brev av Warren M. Hirsch ^{[ es ]} till George B. Dantzig 1957 och motiverades av analysen av simplexmetoden i linjär programmering , eftersom diametern på en polytop ger en nedre gräns för antal steg som krävs av simplexmetoden. Gissningen är nu känd för att vara falsk i allmänhet.

Hirsch-förmodan bevisades för d < 4 och för olika specialfall, medan de mest kända övre gränserna för diametern endast är subexponentiella i n och d . Efter mer än femtio år tillkännagavs ett motexempel i maj 2010 av Francisco Santos Leal , från University of Cantabria . Resultatet presenterades på konferensen 100 Years in Seattle: the mathematics of Klee and Grünbaum och dök upp i Annals of Mathematics . Specifikt presenterade uppsatsen en 43-dimensionell polytop på 86 fasetter med en diameter på mer än 43. Motexemplet har inga direkta konsekvenser för analysen av simplexmetoden, eftersom det inte utesluter möjligheten av en större men ändå linjär resp. polynom antal steg.

Olika ekvivalenta formuleringar av problemet hade getts, såsom d -stegsförmodan, som säger att diametern på en 2 d -facetter polytop i d -dimensionell euklidisk rymd inte är mer än d ; Santos Leals motexempel motbevisar också denna gissning.

Uttalande av gissningen

Grafen för en konvex polytop $P$ är vilken graf som helst vars hörn är i bijektion med hörnen på $\displaystyle P}$ { på ett sådant sätt att två av grafens hörn sammanfogas av en kant om och endast om de två motsvarande hörn av $P$ är förenade av en kant på polytopen. Diametern för $P$ , betecknad $\delta (P)$ ( , är diametern på vilken som helst av dess grafer Dessa definitioner är väldefinierade eftersom två grafer av samma polytop måste vara isomorfa som grafer. Vi kan sedan ange Hirsch-förmodan enligt följande:

Gissning Låt $P$ vara en d -dimensionell konvex polytop med n fasetter. Då $\delta (P)\leq nd$ .

Till exempel har en kub i tre dimensioner sex fasetter. Hirsch-förmodan indikerar då att diametern på denna kub inte kan vara större än tre. Att acceptera gissningen skulle innebära att alla två hörn av kuben kan förbindas med en väg från vertex till vertex med högst tre steg. För alla polytoper med dimensionen minst 8 är denna gräns faktiskt optimal; ingen polytop med dimensionen $d\geq 8$ har en diameter som är mindre än nd , där n är antalet fasetter, som tidigare. Med andra ord, för nästan alla fall tillhandahåller gissningen det minsta antalet steg som behövs för att förena två hörn av en polytop med en bana längs dess kanter. Eftersom simplexmetoden huvudsakligen fungerar genom att konstruera en väg från någon vertex av det möjliga området till en optimal punkt, skulle Hirsch-förmodan ge en nedre gräns som behövs för att simplexmetoden ska avslutas i värsta fall.

Hirsch-förmodan är ett specialfall av polynomet Hirsch-förmodan , som hävdar att det finns något positivt heltal k så att för alla polytoper ${\displaystyle P} ,$ $\delta (P)=O(n^{k})$ , där n är antalet fasetter av P .

Framsteg och delresultat

Hirsch gissningen har visat sig vara sann för ett antal fall. Till exempel uppfyller alla polytop med dimension 3 eller lägre gissningen. Vilken d -dimensionell polytop som helst med n fasetter så att $nd\leq 6$ även uppfyller antagandet.

Andra försök att lösa gissningen manifesterades av en önskan att formulera ett annat problem vars lösning skulle innebära Hirsch-förmodan. Ett exempel av särskild betydelse är d-step-förmodan , en uppmjukning av Hirsch-förmodan som faktiskt har visat sig vara likvärdig med den.

Sats Följande påståenden är ekvivalenta:

$\delta (P)\leq nd$ för alla d -dimensionella polytoper $P$ med n fasetter.
$\delta (P)\leq d$ för alla d -dimensionella polytoper $P$ med 2d fasetter.

Med andra ord, för att bevisa eller motbevisa Hirsch-förmodan behöver man bara överväga polytoper med exakt dubbelt så många facetter som dess dimension. En annan betydande avslappning är att Hirsch-förmodan gäller för alla polytoper om och endast om det gäller för alla enkla polytoper .

Motexempel

Oktaedern är ett av de mest kända exemplen på en spindel .

Tyvärr är Hirsch-förmodan inte sann i alla fall, vilket visades av Francisco Santos 2011. Santos explicita konstruktion av ett motexempel kommer både från det faktum att gissningen kan vara avslappnad för att endast beakta enkla polytoper, och från ekvivalens mellan Hirsch och d -stegsgissningar. I synnerhet producerar Santos sitt motexempel genom att undersöka en viss klass av polytoper som kallas spindlar .

Definition En d -spindel är en d -dimensionell polytop $P$ för vilken det finns ett par distinkta hörn så att varje fasett av $P$ innehåller exakt en av dessa två hörn.

Längden på den kortaste vägen mellan dessa två hörn kallas spindelns längd . Motbevisningen av Hirsch-förmodan bygger på följande teorem, kallad det starka d-stegssatsen för spindlar .

Sats (Santos) Låt $P$ vara en d -spindel. Låt n vara antalet av dess fasetter, och låt l vara dess längd. Sedan finns det en $(nd)$ -spindel, $P'$ , med $2n-2d$ fasetter och en längd som avgränsas nedan av $l+n-2d$ . I synnerhet, om $l>d$ , så bryter ${\displaystyle P'} mot$ d -stegsförmodan.

Santos fortsätter sedan med att konstruera en 5-dimensionell spindel med längden 6, vilket bevisar att det finns en annan spindel som fungerar som ett motexempel till Hirsch-förmodan. Den första av dessa två spindlar har 48 fasetter och 322 hörn, medan spindeln som faktiskt motbevisar gissningen har 86 fasetter och är 43-dimensionell. Detta motexempel motbevisar inte polynomen Hirsch-förmodan, som förblir ett öppet problem.

Anteckningar

Dantzig, George B. (1963), Linear Programming and Extensions , Princeton Univ. Tryck på . Omtryckt i serien Princeton Landmarks in Mathematics , Princeton University Press, 1998.
Kalai, Gil (10 maj 2010). "Francisco Santos motbevisar Hirsch-förmodan" . Hämtad 11 maj 2010 .
Kalai, Gil ; Kleitman, Daniel J. (1992), "A quasi-polynomial bound for the diameter of graphs of polyhedra", Bulletin of the American Mathematical Society , 26 (2): 315–316, arXiv : math/9204233 , doi : 10.1090/ S0273-0979-1992-00285-9 , MR 1130448 , S2CID 37821778 .
Klee, Victor ; Walkup, David W. (1967), "The d -step conjecture for polyhedra of dimension d < 6", Acta Mathematica , 133 : 53–78, doi : 10.1007/BF02395040 , MR 0206823 .
Miranda, Eva (2012), "The Hirsch conjecture has been disproved: An interview with Francisco Santos" (PDF) , Newsletter of the European Mathematical Society (86): 31–36 .
" The Hirsch conjecture is true for (0,1)-polytopes", Mathematical Programming , 45 (1): 109–110, doi : 10.1007/BF01589099 , MR 1017214 , 6328644 .
Santos, Francisco (2011), "A counterexample to the Hirsch conjecture", Annals of Mathematics , Princeton University and Institute for Advanced Study, 176 (1): 383–412, arXiv : 1006.2814 , doi : 10.4007/annals.7612. , MR 2925387 , S2CID 15325169
Ziegler, Günter M. (1994), "The Hirsch Conjecture", Lectures on Polytopes , Graduate Texts in Mathematics, vol. 152, Springer-Verlag, s. 83–93 .