Kombinatorik af polyedre

Kombinatorik af polyedre  er en gren af ​​matematikken , der hører til kombinatorik og kombinatorisk geometri og studerer spørgsmålene om at tælle og beskrive ansigterne af konvekse polyedre .

Forskning i polyedres kombinatorik falder i to grene. Matematikere, der arbejder i dette felt, studerer polyedres kombinatorik ; for eksempel leder de efter uligheder , der beskriver forholdet mellem antallet af hjørner, kanter og flader af forskellige dimensioner i et vilkårligt polyeder, og studerer også andre kombinatoriske egenskaber ved polyedre, såsom forbindelse og diameter (antallet af trin, der kræves for at nå et hvilket som helst toppunkt fra ethvert andet toppunkt). Derudover bruger mange dataloger udtrykket "kombinatorik af polyedre" til at beskrive forskning i den nøjagtige beskrivelse af ansigterne af visse visse polyedre (især 0-1 polyedre, hvis toppunkter er undergrupper af hyperkuben ) som følge af programmeringsproblemer med heltal .

Ansigter og ansigtstællingsvektorer

En flade af et konveks polyeder P kan defineres som skæringspunktet mellem P og et lukket halvrum H , således at grænsen for H ikke indeholder nogen indre punkter af P. Dimensionen af ​​et ansigt er lig med dimensionen af ​​dette skæringspunkt. 0-dimensionelle flader er selve hjørnerne, mens 1-dimensionelle flader (kaldet kanter ) er linjesegmenter, der forbinder par af hjørner. Bemærk, at denne definition inkluderer tomme sæt og hele polytopen P som flader . Hvis P har dimension d , kaldes flader af P med dimension d  − 1 facetter af P , og flader af dimension d  − 2 kaldes kamme [1] . P -fladerne kan delvist ordnes ved inklusion, der danner et fladegitter med selve polyederet P øverst og det tomme sæt nederst.

Nøglemetoden til kombinatorik af polytoper er overvejelsen af ​​ƒ-vektoren for polytopen [2]  — vektoren ( f 0 , f 1 , …, f d  − 1 ), hvor f i er antallet af i - dimensionelle flader af polytopen. For eksempel har en terning otte hjørner, tolv kanter og seks flader (affasninger), så dens ƒ-vektor er (8,12,6). Det dobbelte polyeder har en ƒ-vektor med de samme tal i omvendt rækkefølge. Så for eksempel har det regulære oktaeder , dobbelt til terningen, ƒ-vektoren (6,12,8). Den udvidede ƒ-vektor dannes ved at tilføje en til begge ender af ƒ-vektoren, hvilket svarer til opregning af objekter på alle niveauer af fladegitteret: f −1  = 1 afspejler det tomme sæt som en flade, mens f d  = 1 afspejler P selv . For en terning er den udvidede ƒ-vektor (1,8,12,6,1), og for et oktaeder er det (1,6,12,8,1). Selvom vektorerne i disse eksempler er unimodale (elementer fra venstre mod højre øges først og falder derefter), er der højere-dimensionelle polyedre, for hvilke dette ikke er sandt [3] .

For simple polytoper (polytoper, hvor hver side er en simplex ), transformeres denne vektor ofte til en h -vektor . Hvis vi betragter elementerne i ƒ-vektoren (uden en endelig 1) som koefficienterne for polynomiet ƒ( x ) = Σ f i x d  −  i  − 1 (f.eks. for et oktaeder giver dette polynomiet ƒ( x ) =  x 3  + 6 x 2  + 12 x  + 8), så indeholder h -vektoren koefficienterne for polynomiet h ( x ) = ƒ( x  − 1) (igen, for et oktaeder, h ( x ) =  x 3  + 3 x 2  + 3 x  + 1) [4] . Som Ziegler skriver, "for forskellige problemer med simple polytoper er h -vektorer meget mere bekvemme til at give information om antallet af ansigter end f-vektorer."

Lighed og ulighed

Det vigtigste forhold mellem koefficienterne for ƒ-vektoren i et polyeder er Euler-formlen Σ(−1) i f i = 0, hvor summeringen er over elementerne i den udvidede ƒ-vektor. I tre dimensioner vil bevægelse af to 1'ere fra venstre og højre side af den udvidede ƒ-vektor (1, v , e , f , 1) til højre side af ligheden transformere ligheden til den mere velkendte v − e + f = 2. Af det faktum, at enhver flade af et 3D-polyeder har mindst tre kanter, følger det, at 2 e ≥ 3 f . Ved at bruge dette udtryk til at eliminere e og f fra Eulers formel, får vi e ≤ 3 v − 6 og f ≤ 2 v − 4. På grund af dualiteten af ​​e ≤ 3 f − 6 og v ≤ 2 f − 4. Steinitz' sætning indebærer at enhver A 3-dimensionel heltalsvektor, der opfylder disse ligheder og uligheder, er ƒ-vektoren for et konveks polyeder [5] .

I højere dimensioner bliver andre forhold mellem antallet af flader af et polyeder vigtige, herunder Dehn-Somerville-ligningen , der, udtrykt i h-vektorer af simple polytoper, har den simple form h k = h d − k for evt . k . Varianten af ​​disse ligninger med k = 0 svarer til Euler-formlen, men for d > 3 er disse ligninger lineært uafhængige af hinanden og pålægger h -vektoren yderligere begrænsninger (og derfor også ƒ-vektoren) [4] .

En anden vigtig ulighed for antallet af flader af en polytop kommer fra den øvre grænsesætning først bevist af McMullen [6] , som siger, at en d -dimensionel polytop med n hjørner ikke kan have flere flader af nogen dimension end en tilstødende polytop med samme antal hjørner:

hvor asterisken betyder, at summens sidste led skal halveres, hvis d er lige [7] . Det følger asymptotisk, at der ikke kan være mere end ansigter af alle dimensioner.

Selv for dimension fire udgør sættet af alle mulige ƒ-vektorer af konvekse polyedre ikke en konveks delmængde af det firedimensionelle heltalsgitter, og meget er fortsat uklart om de mulige værdier af disse vektorer [8] .

Egenskaber fra grafteori

Sammen med antallet af ansigter af polyedre studerer forskere også deres andre kombinatoriske egenskaber, såsom egenskaberne af grafer opnået fra hjørnerne og kanterne af polyedre (deres 1-skelet ).

Balinskys sætning siger, at en graf opnået på denne måde fra ethvert d - dimensionelt konveks polyeder er vertex - d -forbundet [9] [10] . I tilfælde af 3-polytoper kan denne egenskab og planaritet bruges til nøjagtigt at beskrive polytopgrafer — Steinitz' sætning siger, at G er skelettet af en 3-polytop, hvis og kun hvis G er en top-3-forbundet plan graf [11 ] .

Blind og Money-Levitsks sætning [12] (angivet som en formodning af Micha Perles) siger, at det er muligt at rekonstruere ansigtsstrukturen af ​​en simpel polytop ud fra dens graf. Det vil sige, at hvis en given urettet graf er skelettet af en simpel polytop, er der kun én polytop (op til kombinatorisk ækvivalens), for hvilken grafen fungerer som skelettet. Denne egenskab står i skarp kontrast til egenskaberne for tilstødende (ikke simple) polytoper, hvis grafer er komplette  - der kan være mange forskellige tilstødende polyedre med den samme graf. Et andet bevis for denne sætning blev givet af Kalai [13] , og Friedman [14] viste, hvordan man bruger denne sætning til at skabe en polynomisk tidsalgoritme til at konstruere simple polyedre ud fra deres grafer.

I sammenhæng med simplex lineær programmering er det vigtigt at overveje diameteren af ​​et polyeder, det mindste antal hjørner, der skal krydses for at nå ethvert hjørne fra ethvert andet vertex. Systemet med lineære uligheder i et lineært programmeringsproblem bestemmer polyederens overflader af tilladelige løsninger på problemet, og simpleksmetoden finder den optimale løsning, idet den passerer langs kanterne af denne polyhedron. Diameteren evaluerer således den nedre grænse for antallet af trin i denne metode. Den tilbageviste Hirsch-formodning gav en stærk øvre grænse for diameteren [15] . En svagere (kvasi-polynomium) øvre grænse for diameteren er kendt [16] , og Hirsch-formodningen er blevet bevist for visse klasser af polyedre [17] .

Beregningsmæssige egenskaber

At bestemme, om antallet af hjørner af et givet polyeder er afgrænset af et naturligt tal k , er en vanskelig opgave og hører til kompleksitetsklassen PP [18] .

Ansigter af 0-1 polyedre

Det er vigtigt i forbindelse med cutoff-metoder til heltalsprogrammering nøjagtigt at kunne beskrive affasningerne (flader) af polyederet, hvorpå toppunkterne ligger, svarende til løsningerne af kombinatoriske optimeringsproblemer. Ofte har sådanne problemer løsninger, der kan gives af bitvektorer , og de tilsvarende polyedre har hjørner, hvis koordinater er tallene nul og en.

Som et eksempel, tag Birkhoff polyhedron , et sæt af n  ×  n matricer, der kan dannes af konvekse kombinationer af permutationsmatricer . På samme måde kan hjørnerne af denne polytop forstås som en beskrivelse af alle perfekte matchninger af den komplette todelte graf , og det lineære optimeringsproblem på denne polytop kan betragtes som et problem med at finde en vægtet minimum perfekt matchning. Birkhoffs sætning siger, at et sådant polyeder kan beskrives ved hjælp af to typer lineære uligheder. For det første er hvert element i matrixen ikke-negativt, og for det andet, for hver kolonne og for hver række, er summen af ​​matrixelementerne lig med én. Restriktioner på summen over rækker og søjler definerer et lineært underrum med dimension n 2  − 2 n  + 1, hvori Birkhoff-polyederet ligger, og begrænsninger på matrixelementernes ikke-negativitet definerer polytopens flader i dette underrum.

Birkhoff-polyederet er usædvanligt, idet en fuldstændig beskrivelse af dets ansigter er kendt. For mange andre 0-1 polyedre er der eksponentielt (eller supereksponentielt) mange ansigter, og kun en delvis beskrivelse af dem er tilgængelig [19] .

Se også

Noter

  1. ↑ Ziegler, 1995 , s. 51.
  2. ↑ Ziegler, 1995 , s. 245-246.
  3. ↑ Ziegler, 1995 , s. 272.
  4. ↑ 12 Ziegler , 1995 , s. 246-253.
  5. ↑ Steinitz, 1906 .
  6. ↑ McMullen, 1970 .
  7. ↑ Ziegler, 1995 , s. 254-258.
  8. ↑ Höppner, Ziegler, 2000 .
  9. ↑ Balinski, 1961 .
  10. ↑ Ziegler, 1995 , s. 95-96.
  11. ↑ Ziegler, 1995 , s. 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 og Kiefer 2015 , s. Thm. 5.
  19. ↑ Ziegler, 2000 .

Litteratur

Links