Combinatoria poliedrelor

Combinatoria poliedrelor  este o ramură a matematicii care aparține combinatoriei și geometriei combinatorii și studiază problemele numărării și descrierii fețelor poliedrelor convexe .

Cercetarea în combinatoria poliedrelor se încadrează în două ramuri. Matematicienii care lucrează în acest domeniu studiază combinatoria poliedrelor; de exemplu, ei caută inegalități care descriu relația dintre numărul de vârfuri, muchii și fețe de dimensiuni diferite într-un poliedru arbitrar și, de asemenea, studiază alte proprietăți combinatorii ale poliedrelor, cum ar fi conectivitatea și diametrul (numărul de pași necesari pentru a ajunge la orice vârf de la orice alt vârf). În plus, mulți informaticieni folosesc sintagma „combinatorie a poliedrelor” pentru a descrie cercetarea privind descrierea exactă a fețelor anumitor poliedre (în special poliedre 0-1, ale căror vârfuri sunt subseturi ale hipercubului ) care decurg din probleme de programare cu numere întregi .

Fețe și vectori de numărare a fețelor

O față a unui poliedru convex P poate fi definită ca intersecția lui P și a unui semi-spațiu închis H astfel încât limita lui H să nu conțină puncte interioare ale lui P. Dimensiunea unei fețe este egală cu dimensiunea acestei intersecții. Fețele 0-dimensionale sunt vârfurile în sine, în timp ce fețele 1-dimensionale (numite muchii ) sunt segmente de linie care conectează perechi de vârfuri. Rețineți că această definiție include mulțimi goale și întregul politop P ca fețe . Dacă P are dimensiunea d , fețele lui P cu dimensiunea d  − 1 se numesc fațete ale lui P , iar fețele cu dimensiunea d  − 2 se numesc creste [1] . Fețele lui P pot fi ordonate parțial prin includere, formând o rețea de față cu poliedrul P însuși în partea de sus și setul gol în partea de jos.

Metoda cheie a combinatoriei politopilor este luarea în considerare a vectorului ƒ al politopului [2]  — vectorul ( f 0 , f 1 , …, f d  − 1 ), unde f i este numărul de fețe i - dimensionale a politopului. De exemplu, un cub are opt vârfuri, douăsprezece muchii și șase fețe (teșituri), deci vectorul său ƒ este (8,12,6). Poliedrul dual are un vector ƒ cu aceleași numere în ordine inversă. Deci, de exemplu, octaedrul regulat , dual cubului, are vectorul ƒ (6,12,8). Vectorul ƒ extins este format prin adăugarea unor capete la ambele capete ale vectorului ƒ, ceea ce corespunde enumerarii obiectelor de la toate nivelurile rețelei feței: f −1  = 1 reflectă mulțimea goală ca o față, în timp ce f d  = 1 reflectă P însuși . Pentru un cub, vectorul ƒ extins este (1,8,12,6,1), iar pentru un octaedru este (1,6,12,8,1). Deși vectorii acestor exemple sunt unimodali (elementele de la stânga la dreapta mai întâi cresc și apoi descresc), există poliedre de dimensiuni mai mari pentru care acest lucru nu este adevărat [3] .

Pentru politopii simpli (politopuri în care fiecare față este un simplex ), acest vector este adesea transformat pentru a forma un h -vector. Dacă considerăm elementele vectorului ƒ (fără un 1 finit) ca coeficienți ai polinomului ƒ( x ) = Σ f i x d  −  i  − 1 (de exemplu, pentru un octaedru, aceasta dă polinomul ƒ( x ) ) =  x 3  + 6 x 2  + 12 x  + 8), atunci vectorul h conține coeficienții polinomului h ( x ) = ƒ( x  − 1) (din nou, pentru un octaedru, h ( x ) =  x 3  + 3 x 2  + 3 x  + 1) [4] . După cum scrie Ziegler, „pentru diverse probleme despre politopii simpli, vectorii h sunt mult mai convenabil pentru a oferi informații despre numărul de fețe decât vectorii f”.

Egalități și inegalități

Cel mai important raport al coeficienților vectorului ƒ al unui poliedru este formula lui Euler Σ(−1) i f i = 0, unde însumarea este peste elementele vectorului ƒ extins. În trei dimensiuni, mutarea a doi 1 din partea stângă și dreaptă a vectorului ƒ extins (1, v , e , f , 1) în partea dreaptă a egalității transformă egalitatea în mai familiar v − e + f = 2. Din faptul că orice față a unui poliedru 3D are cel puțin trei muchii, rezultă că 2 e ≥ 3 f . Folosind această expresie pentru a elimina e și f din formula lui Euler, obținem e ≤ 3 v − 6 și f ≤ 2 v − 4. Datorită dualității e ≤ 3 f − 6 și v ≤ 2 f − 4. Teorema lui Steinitz implică că orice vector întreg tridimensional care satisface aceste egalități și inegalități este vectorul ƒ al unui poliedru convex [5] .

În dimensiuni mai mari, alte relații între numărul de fețe ale unui poliedru devin importante, inclusiv ecuația Dehn-Somerville , care, exprimată în h-vectori ai politopilor simpli, ia forma simplă h k = h d − k pentru orice k . Varianta acestor ecuații cu k = 0 este echivalentă cu formula Euler, dar pentru d > 3 aceste ecuații sunt liniar independente unele de altele și impun restricții suplimentare vectorului h (și deci vectorului ƒ) [4] .

O altă inegalitate importantă pentru numărul de fețe ale unui politop provine din teorema limitei superioare demonstrată pentru prima dată de McMullen [6] , care afirmă că un politop d -dimensional cu n vârfuri nu poate avea mai multe fețe de orice dimensiune decât un adiacent . politop cu același număr de vârfuri:

unde asteriscul înseamnă că ultimul termen al sumei trebuie înjumătățit dacă d este par [7] . Rezultă asimptotic că nu pot exista mai mult decât fețe de toate dimensiunile.

Chiar și pentru dimensiunea patru, mulțimea tuturor ƒ-vectorilor posibili ai poliedrelor convexe nu formează o submulțime convexă a rețelei întregi cu patru dimensiuni și rămân multe neclare cu privire la valorile posibile ale acestor vectori [8] .

Proprietăți din teoria grafurilor

Alături de numărul de fețe ale poliedrelor, cercetătorii studiază și celelalte proprietăți combinatorii ale acestora, cum ar fi proprietățile graficelor obținute din vârfurile și muchiile poliedrelor ( scheletul lor 1 ).

Teorema lui Balinsky afirmă că un graf obținut în acest fel din orice poliedru convex d -dimensional este un vârf - d -conectat [9] [10] . În cazul 3-politopilor, această proprietate și planaritate pot fi utilizate pentru a descrie cu acuratețe graficele politopilor — teorema lui Steinitz afirmă că G este scheletul unui 3-politop dacă și numai dacă G este un graf planar conectat cu 3 vârfuri [11]. ] .

Teorema lui Blind și Money-Levitsk [12] (pronunțată ca o presupunere de Micha Perles) afirmă că este posibil să se reconstruiască structura feței unui politop simplu din graficul său. Adică, dacă un graf nedirecționat dat este scheletul unui politop simplu, există un singur politop (până la echivalența combinatorie) pentru care graficul servește ca schelet. Această proprietate este în contrast puternic cu proprietățile politopilor adiacenți (nu simple) ale căror grafice sunt complete  - pot exista multe poliedre adiacente diferite cu același grafic. O altă dovadă a acestei teoreme a fost dată de Kalai [13] , iar Friedman [14] a arătat cum se utilizează această teoremă pentru a crea un algoritm de timp polinomial pentru construirea poliedrelor simple din graficele lor.

În contextul programării liniare simplex , este important să se ia în considerare diametrul unui poliedru, numărul minim de vârfuri care trebuie parcurs pentru a ajunge la orice vârf de la orice alt vârf. Sistemul de inegalități liniare ale unei probleme de programare liniară determină fețele poliedrului soluțiilor admisibile ale problemei, iar metoda simplex găsește soluția optimă, trecând de-a lungul muchiilor acestui poliedr. Astfel, diametrul evaluează limita inferioară a numărului de trepte ale acestei metode. Conjectura Hirsch respinsă a dat o limită superioară puternică a diametrului [15] . O limită superioară mai slabă (cvasi-polinom) pentru diametru este cunoscută [16] , iar conjectura Hirsch a fost dovedită pentru anumite clase de poliedre [17] .

Proprietăți computaționale

Determinarea dacă numărul de vârfuri ale unui poliedru dat este mărginit de un număr natural k este o sarcină dificilă și aparține clasei de complexitate PP [18] .

Fețe de 0-1 poliedre

Este important în contextul metodelor cutoff pentru programarea întregilor să se poată descrie cu acuratețe teșiturile (fețele) poliedrului, pe care se află vârfurile, corespunzătoare soluțiilor problemelor de optimizare combinatorie. Adesea, astfel de probleme au soluții care pot fi date de vectori de biți , iar poliedrele corespunzătoare au vârfuri ale căror coordonate sunt numerele zero și unu.

Ca exemplu, luăm poliedrul Birkhoff , un set de n  ×  n matrice care poate fi format din combinații convexe de matrici de permutare . În mod similar, vârfurile acestui politop pot fi înțelese ca o descriere a tuturor potrivirilor perfecte ale graficului bipartit complet , iar problema de optimizare liniară pe acest politop poate fi considerată ca o problemă de găsire a unei potriviri perfecte minime ponderate. Teorema lui Birkhoff afirmă că un astfel de poliedru poate fi descris folosind două tipuri de inegalități liniare. În primul rând, fiecare element al matricei este nenegativ, iar în al doilea rând, pentru fiecare coloană și pentru fiecare rând, suma elementelor matricei este egală cu unu. Restricțiile privind suma peste rânduri și coloane definesc un subspațiu liniar de dimensiunea n 2  − 2 n  + 1 în care se află poliedrul Birkhoff, iar restricțiile privind nenegativitatea elementelor matricei definesc fețele politopului din acest subspațiu.

Poliedrul Birkhoff este neobișnuit prin faptul că se cunoaște o descriere completă a fețelor sale. Pentru multe alte poliedre 0-1, există exponențial (sau supraexponențial) multe fețe și este disponibilă doar o descriere parțială a acestora [19] .

Vezi și

Note

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

Literatură

Link -uri