Kombinatorik av polyedrar

Kombinatorik av polyedrar  är en gren av matematiken som hör till kombinatorik och kombinatorisk geometri och studerar frågorna om att räkna och beskriva ansikten på konvexa polyedrar .

Forskning inom polyedrarnas kombinatorik delas in i två grenar. Matematiker som arbetar inom detta område studerar polyedrarnas kombinatorik ; till exempel letar de efter ojämlikheter som beskriver förhållandet mellan antalet hörn, kanter och ytor av olika dimensioner i en godtycklig polyeder, och studerar även andra kombinatoriska egenskaper hos polyedrar, såsom anslutning och diameter (antalet steg som krävs för att nå vilken vertex som helst från vilken annan vertex som helst). Dessutom använder många forskare som arbetar inom datavetenskap frasen "kombinatorik av polyedrar" för att beskriva forskning om den exakta beskrivningen av ansiktena på vissa vissa polyedrar (särskilt 0-1 polyedrar, vars hörn är delmängder avhypercube ) som härrör från heltalsprogrammeringsproblem .

Ansikten och ansiktsräkningsvektorer

En yta av en konvex polyeder P kan definieras som skärningspunkten mellan P och ett slutet halvrum H så att gränsen för H inte innehåller några inre punkter av P. Dimensionen på ett ansikte är lika med dimensionen för denna korsning. 0-dimensionella ytor är själva hörnen, medan 1-dimensionella ytor (kallade kanter ) är linjesegment som förbinder par av hörn. Observera att denna definition inkluderar tomma uppsättningar och hela polytopen P som ytor . Om P har dimensionen d  kallas ytorna på P med dimensionen d − 1 fasetter av P , och ytorna på dimensionen d  − 2 kallas åsar [1] . Ytorna på P kan partiellt ordnas genom inkludering och bildar ett ytgitter med själva polyedern P överst och den tomma uppsättningen längst ner.

Nyckelmetoden för kombinatorik av polytoper är beaktandet av ƒ-vektorn för polytopen [2]  — vektorn ( f 0 , f 1 , …, f d  − 1 ), där fi är antalet i - dimensionella ytor av polytopen. Till exempel har en kub åtta hörn, tolv kanter och sex ytor (fasning), så dess ƒ-vektor är (8,12,6). Den dubbla polyedern har en ƒ-vektor med samma tal i omvänd ordning. Så, till exempel, den vanliga oktaedern , dubbel till kuben, har ƒ-vektorn (6,12,8). Den utökade ƒ-vektorn bildas genom att lägga till ettor till båda ändarna av ƒ-vektorn, vilket motsvarar uppräkningen av objekt på alla nivåer av ansiktsgittret: f −1  = 1 reflekterar den tomma mängden som ett ansikte, medan f d  = 1 reflekterar P själv . För en kub är den utökade ƒ-vektorn (1,8,12,6,1), och för en oktaeder är den (1,6,12,8,1). Även om vektorerna i dessa exempel är unimodala (element från vänster till höger ökar först och minskar sedan), finns det flerdimensionella polyedrar för vilka detta inte är sant [3] .

För enkla polytoper (polytoper där varje sida är en simplex ) transformeras denna vektor ofta för att bilda en h -vektor. Om vi ​​betraktar elementen i ƒ-vektorn (utan en ändlig 1) som koefficienterna för polynomet ƒ( x ) = Σ f i x d  −  i  − 1 (till exempel för en oktaeder ger detta polynomet ƒ( x ) =  x 3  + 6 x 2  + 12 x  + 8), då innehåller h -vektorn koefficienterna för polynomet h ( x ) = ƒ( x  − 1) (återigen, för en oktaeder, h ( x ) =  x 3  + 3 x 2  + 3 x  + 1) [4] . Som Ziegler skriver, "för olika problem med enkla polytoper är h -vektorer mycket bekvämare för att ge information om antalet ansikten än f-vektorer."

Jämlikheter och ojämlikheter

Det viktigaste förhållandet mellan koefficienterna för en polyeders ƒ-vektor är Eulerformeln Σ(−1) i f i = 0, där summeringen är över elementen i den utökade ƒ-vektorn. I tre dimensioner, när två 1:or flyttas från vänster och höger sida av den utökade ƒ-vektorn (1, v , e , f , 1) till höger sida av likheten omvandlas likheten till den mer välbekanta v − e + f = 2. Av det faktum att en yta av en 3D-polyeder har minst tre kanter, följer att 2 e ≥ 3 f . Genom att använda detta uttryck för att eliminera e och f från Eulers formel får vi e ≤ 3 v − 6 och f ≤ 2 v − 4. På grund av dualiteten av e ≤ 3 f − 6 och v ≤ 2 f − 4. Steinitz sats antyder att varje A 3-dimensionell heltalsvektor som uppfyller dessa likheter och olikheter är ƒ-vektorn för en konvex polyeder [5] .

I högre dimensioner blir andra relationer mellan antalet ytor av en polyeder viktiga, inklusive Dehn-Somerville-ekvationen , som, uttryckt i termer av h-vektorer för enkla polytoper, tar den enkla formen h k = h d − k för alla k . Varianten av dessa ekvationer med k = 0 är ekvivalent med Eulerformeln, men för d > 3 är dessa ekvationer linjärt oberoende av varandra och lägger ytterligare begränsningar på h -vektorn (och därför på ƒ-vektorn) [4] .

En annan viktig ojämlikhet för antalet ytor av en polytop kommer från den övre gränssatsen först bevisad av McMullen [6] , som säger att en d -dimensionell polytop med n hörn inte kan ha fler ytor av någon dimension än en intilliggande polytop med samma antal hörn:

där asterisken betyder att summans sista term måste halveras om d är jämnt [7] . Det följer asymptotiskt att det inte kan finnas mer än ansikten av alla dimensioner.

Även för dimension fyra bildar inte uppsättningen av alla möjliga ƒ-vektorer av konvexa polyedrar en konvex delmängd av det fyrdimensionella heltalsgittret, och mycket är fortfarande oklart om de möjliga värdena för dessa vektorer [8] .

Egenskaper från grafteori

Tillsammans med antalet ytor på polyedrar studerar forskare också deras andra kombinatoriska egenskaper, såsom egenskaperna hos grafer som erhålls från hörn och kanter på polyedrar (deras 1-skelett ).

Balinskys teorem säger att en graf som erhålls på detta sätt från vilken d -dimensionell konvex polyeder som helst är vertex - d -kopplad [9] [10] . I fallet med 3-polytoper kan denna egenskap och planaritet användas för att korrekt beskriva polytopgrafer — Steinitzs teorem säger att G är skelettet av en 3-polytop om och endast om G är en vertex-3-kopplad plan graf [11 ] .

Blind och Money-Levitsks teorem [12] (angiven som en gissning av Micha Perles) säger att det är möjligt att rekonstruera ansiktsstrukturen för en enkel polytop från dess graf. Det vill säga, om en given oriktad graf är skelettet av en enkel polytop, finns det bara en polytop (upp till kombinatorisk ekvivalens) för vilken grafen fungerar som skelettet. Denna egenskap står i skarp kontrast till egenskaperna hos intilliggande (inte enkla) polytoper vars grafer är kompletta  — det kan finnas många olika intilliggande polyedrar med samma graf. Ett annat bevis för denna sats gavs av Kalai [13] , och Friedman [14] visade hur man använder denna sats för att skapa en polynomisk tidsalgoritm för att konstruera enkla polyedrar från deras grafer.

I samband med simplex linjär programmering är det viktigt att överväga diametern på en polyeder, det minsta antalet hörn som måste korsas för att nå någon vertex från någon annan vertex. Systemet med linjära olikheter för ett linjärt programmeringsproblem bestämmer ytorna på polyedern av tillåtna lösningar på problemet, och simplexmetoden hittar den optimala lösningen, passerar längs kanterna på denna polyeder. Således utvärderar diametern den nedre gränsen för antalet steg i denna metod. Den vederlagda Hirsch-förmodan gav en stark övre gräns för diametern [15] . En svagare (kvasipolynom) övre gräns för diametern är känd [16] , och Hirsch-förmodan har bevisats för vissa klasser av polyedrar [17] .

Beräkningsegenskaper

Att avgöra om antalet hörn av en given polyeder är begränsat av något naturligt tal k är en svår uppgift och tillhör komplexitetsklassen PP [18] .

Ansikter av 0-1 polyedrar

Det är viktigt i samband med cutoff-metoder för heltalsprogrammering att noggrant kunna beskriva avfasningarna (ytorna) av polyedern, på vilken hörnen ligger, motsvarande lösningarna av kombinatoriska optimeringsproblem. Ofta har sådana problem lösningar som kan ges av bitvektorer , och motsvarande polyedrar har hörn vars koordinater är siffrorna noll och ett.

Som ett exempel, ta Birkhoff polyhedron , en uppsättning av n  ×  n matriser som kan bildas av konvexa kombinationer av permutationsmatriser . På liknande sätt kan hörnen av denna polytop förstås som en beskrivning av alla perfekta matchningar av den fullständiga tvådelade grafen , och det linjära optimeringsproblemet på denna polytop kan betraktas som ett problem med att hitta en viktad minimal perfekt matchning. Birkhoffs teorem säger att en sådan polyeder kan beskrivas med hjälp av två typer av linjära olikheter. För det första är varje element i matrisen icke-negativt, och för det andra, för varje kolumn och för varje rad, är summan av matriselementen lika med en. Restriktioner för summan över rader och kolumner definierar ett linjärt delrum med dimensionen n 2  − 2 n  + 1 i vilket Birkhoff-polyedern ligger, och restriktioner för matriselementens icke-negativitet definierar polytopens ytor i detta delrum.

Birkhoff-polyedern är ovanlig eftersom en fullständig beskrivning av dess ansikten är känd. För många andra 0-1 polyedrar finns det exponentiellt (eller superexponentiellt) många ansikten, och endast en partiell beskrivning av dem är tillgänglig [19] .

Se även

Anteckningar

  1. ↑ Ziegler, 1995 , sid. 51.
  2. ↑ Ziegler, 1995 , sid. 245–246.
  3. ↑ Ziegler, 1995 , sid. 272.
  4. ↑ 12 Ziegler , 1995 , sid. 246–253.
  5. ↑ Steinitz, 1906 .
  6. ↑ McMullen, 1970 .
  7. ↑ Ziegler, 1995 , sid. 254–258.
  8. ↑ Höppner, Ziegler, 2000 .
  9. ↑ Balinski, 1961 .
  10. ↑ Ziegler, 1995 , sid. 95–96.
  11. ↑ Ziegler, 1995 , sid. 103–126.
  12. ↑ Blind, Mani-Levitska, 1987 .
  13. ↑ Kalai, 1988 .
  14. ↑ Friedman, 2009 .
  15. ↑ Santos, 2012 .
  16. ↑ Kalai, Kleitman, 1992 .
  17. ↑ Naddef (1989) .
  18. ↑ Haase och Kiefer 2015 , sid. Thm. 5.
  19. ↑ Ziegler, 2000 .

Litteratur

Länkar