Permutoedru
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4f/Symmetric_group_4%3B_permutohedron_3D%3B_transpositions_%281-based%29.png/300px-Symmetric_group_4%3B_permutohedron_3D%3B_transpositions_%281-based%29.png)
În matematică permutoedrul de ordinul n este un politop (n−1)-dimensional conținut într-un spațiu n-dimensional. Coordonatele vârfurilor sale (vârfuri etichetate în imaginea din dreapta) sunt permutări ale primelor n numere naturale. Laturile identifică cele mai scurte drumuri posibile (ansambluri de transpoziții) care leagă două vârfuri (permutări). Două permutări legate printr-o latură diferă doar în două locuri (o transpunere), iar numerele de pe aceste locuri sunt vecine (diferă ca valoare cu 1).
Imaginea din dreapta arată permutoedrul de ordinul 4, care este octaedrul trunchiat. Vârfurile sale sunt cele 24 de permutări ale lui (1, 2, 3, 4). Laturile paralele au aceeași culoare. Cele 6 culori ale laturilor corespund celor 6 posibile transpoziții a 4 elemente, adică indică în ce două locuri diferă permutările conectate. (De exemplu, latorile roșii conectează permutări care diferă în ultimele două locuri.)
Deși terminația -edru dă impresia că permutoedrul ar fi un poliedru, adică o figură geometrică tridimensională, el este de fapt un politop.
Istoric
Conform lui Günter Ziegler,[1] permutoedrele au fost studiate pentru prima dată de Pieter Hendrik Schoute.[2] Numele de permutoèdre a fost inventat de Georges Guilbaud și Pierre Rosenstiehl.[3] Ei descriu cuvântul drept un barbarism, dar ușor de reținut și îl supun criticii cititorilor lor.[4]
Permutoedrele sunt uneori numite politopuri de permutare, dar această terminologie este folosită și pentru politopul Birkhoff, definit ca anvelopa convexă a matricilor permutare. Mai general, Joseph Bowman[5] folosește acest termen pentru orice politop ale cărui vârfuri pot fi puse într-o corespondență biunivocă cu permutările unei mulțimi.
Vârfuri, laturi și fațete
vârfuri, laturi, fațete, fețe Dimensiunea feței d = n − k. |
k = 1 2 3 4 5 n 1 1 1 2 1 2 3 3 1 6 6 13 4 1 14 36 24 75 5 1 30 150 240 120 541 |
Permutoedrul de ordinul n are n! vârfuri, fiecare fiind adiacent altor n − 1. Numărul laturilor este (n − 1) n!/2, iar lungimea lor este .
Două vârfuri conectate diferă prin interschimbarea a două coordonate, ale căror valori diferă cu 1.[6] Perechea de locuri interschimbate corespunde direcției laturii. (În imaginea de la începutul articolului vârfurile (3, 2, 1, 4) și (2, 3, 1, 4) sunt conectate printr-o latură albastră și diferă prin interschimbarea lui 2 și 3 de pe primele două locuri. Valorile 2 și 3 diferă cu 1. Toate laturile albastre corespund interschimbărilor de coordonate de pe primele două locuri.)
Numărul de fațete este 2n − 2, deoarece acestea corespund unor submulțimi proprii nevide S din {1 ... n}. Vârfurile unei fațete corespunzătoare submulțimii S au în comun faptul că coordonatele lor pe locurile din S sunt mai mici decât coordonatele din pozițiile care nu sunt în S.[7]
Exemple de fațete | ||||
---|---|---|---|---|
La ordinul 3 fațetele sunt cele 6 laturi, iar la ordinul 4 sunt cele 14 fețe. | ||||
ordinul 3 | ordinul 4 | |||
submulțimi de 1-elemente | submulțimi de 2-elemente | submulțimi de 1-elemente | submulțimi de 2-elemente | submulțimi de 3-elemente |
![]() | ![]() | ![]() | ![]() | ![]() |
Mai general, fețele de dimensiune 0 (vârfurile) până la n − 1 (permutoedrul însuși) corespund ordonării slabe stricte a mulțimii {1 ... n}. Deci numărul tuturor fețelor este al n-lea număr ordonat Bell.[8] O față de dimensiunea d corespunde unei ordonări cu clasa de echivalență k = n − d.
Exemple de fețe | |||||||
---|---|---|---|---|---|---|---|
ordinul 3 | ordinul 4 | ||||||
![]() | ![]() | ||||||
Imaginile de mai sus arată laticele fețelor permutoedrelor de ordinul 3 și 4 (fără fețele vide). Etichetele vârfurilor a | b | c | d interpretate drept permutări (a, b, c, d) sunt cele care formează graful Cayley.
|
Numărul de fețe de dimensiunea d = n − k în permutoedrul de ordin n este dat de triunghiul T:[9]
cu reprezentând numerele Stirling de tipul al doilea.
Este afișat în dreapta împreună cu sumele sale pe rând, numerele Bell ordonate.
Alte proprietăți
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/69/Symmetric_group_4%3B_Cayley_graph_1%2C2%2C6_%281-based%29.png/300px-Symmetric_group_4%3B_Cayley_graph_1%2C2%2C6_%281-based%29.png)
Permutoedrul este tranzitiv pe vârfuri: grupul simetric(d) Sn acționează asupra permutoedrului prin permutarea coordonatelor.
Permutoedrul este un zonotop; o copie translată a permutoedrului poate fi generată ca suma Minkowski(d) a unui număr triunghiular n(n − 1)/2 de segmente care conecteaă perechile de vectori ai bazei standard.[10]
Vârfurile și laturile permutoedrului sunt izomorfe cu unul dintre grafurile Cayley(d) ale grupului simetric, și anume cel generat(d) prin transpoziții care schimbă elemente consecutive. Vârfurile grafului Cayley sunt permutările inverse ale celor din permutoedru.[11] Imaginea din dreapta arată graful Cayley al lui S4. Culorile laturilor sale reprezintă cele 3 transpoziții generatoare: (1, 2), (2, 3), (3, 4).
Acest graf Cayley este un ciclu Hamiltonian. Un asemenea ciclu poate fi găsit prin algoritmul Steinhaus–Johnson–Trotter.
Teselarea spațiului
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/ab/Hexagonal_tiling.svg/145px-Hexagonal_tiling.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Bitruncated_cubic_honeycomb.png/149px-Bitruncated_cubic_honeycomb.png)
Permutoedrul de ordinul n se află în întregime în hiperplanul (n − 1)-dimensional format din toate punctele ale căror coordonate se însumează cu numărul
- 1 + 2 + ... + n = n(n + 1)/2.
Mai mult decât atât, acest hiperplan poate fi teselat de nenumărate copii translate ale permutoedrului. Fiecare dintre ele diferă de permutoedrul de bază printr-un element dintr-o anumită latice (n − 1)-dimensională, care constă din n-tupluri de numere întregi care se însumează la zero și ale căror resturi modulo n sunt toate egale:
- x1 + x2 + ... + xn = 0
- x1 ≡ x2 ≡ ... ≡ xn (mod n).
Aceaste este laticea , laticea duală a laticei . În alte cuvinte, permutoedrul este celula Voronoi(d) pentru . Această latice este uneori numită latice permutoedrică.[12]
Astfel, permutoedrul de ordinul 4 prezentat mai sus teselează spațiul tridimensional prin translație. Aici spațiul tridimensional este subspațiul afin al spațiului cvadridimensional R4 cu coordonatele x, y, z, w care constă din cele 4 tupluri de numere reale a căror sumă este 10,
- x + y + z + w = 10.
Se verifică cu ușurință că pentru fiecare dintre următorii patru vectori,
- (1,1,1,−3), (1,1,−3,1), (1,−3,1,1) and (−3,1,1,1),
suma coordonatelor este zero și toate coordonatele sunt congruente cu 1 (mod 4). Oricare trei dintre acești vectori generează laticea de translație.
Teselările formate în acest fel din permutoedrele de ordinul 2, 3 și 4 sunt apeirogonul, pavarea hexagonală regulată și fagurele cubic bitrunchiat. Teselările duale au toate fațetele simplexuri, deși dincolo de ordinul 3 nu sunt politopuri regulate.
Exemple
Ordinr 2 | Ordin 3 | Ordin 4 | Ordin 5 | Ordin 6 |
---|---|---|---|---|
2 vârfuri | 6 vârfuri | 24 vârfuri | 120 vârfuri | 720 vârfuri |
![]() | ![]() | ![]() | ![]() | ![]() |
segment | hexagon | octaedru trunchiat | 5-celule omnitrunchiat | 5-simplex omnitrunchiat |
Note
- ^ en Ziegler, Günter M. (), Lectures on Polytopes, Springer-Verlag, Graduate Texts in Mathematics 152
- ^ en Schoute, Pieter Hendrik (), „Analytic treatment of the polytopes regularly derived from the regular polytopes”, Verhandelingen der Koninklijke Akademie van Wetenschappen Te Amsterdam, 11 (3): 87 pp Googlebook, 370–381 Also online on the KNAW Digital Library at http://www.dwc.knaw.nl/toegangen/digital-library-knaw/?pagetype=publDetail&pId=PU00011495
- ^ fr Guilbaud, Georges Th.; Rosenstiehl, Pierre (), „Analyse algébrique d'un scrutin”, Mathématiques et Sciences Humaines, 4: 9–33
- ^ În original în franceză le mot permutoèdre est barbare, mais il est facile à retenir; soumettons-le aux critiques des lecteurs.
- ^ en Bowman, V. Joseph (), „Permutation polyhedra”, SIAM Journal on Applied Mathematics, 22 (4): 580–589, doi:10.1137/0122054, JSTOR 2099695, MR 0305800
- ^ en Gaiha & Gupta (1977).
- ^ en Lancia (2018), p. 105 (see chapter The Permutahedron).
- ^ v. de exemplu Ziegler (1995), p. 18.
- ^ Șirul A019538 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
- ^ Ziegler (1995), p. 200.
- ^ Această etichetare a grafului Cayley este prezentată, de exemplu, de Ziegler (1995)
- ^ Baek, Adams & Dolson (2013).
Bibliografie
- en Baek, Jongmin; Adams, Andrew; Dolson, Jennifer (), „Lattice-based high-dimensional Gaussian filtering and the permutohedral lattice”, Journal of Mathematical Imaging and Vision, 46 (2): 211–237, doi:10.1007/s10851-012-0379-2, hdl:1721.1/105344
, MR 3061550
- en Gaiha, Prabha; Gupta, S. K. (), „Adjacent vertices on a permutohedron”, SIAM Journal on Applied Mathematics, 32 (2): 323–327, doi:10.1137/0132025, JSTOR 2100417, MR 0427102 .
- en Lancia, Giuseppe (), Compact extended linear programming models, Cham, Switzerland: Springer, ISBN 978-3-319-63975-8 .
Lectură suplimentară
- en Le Conte de Poly-Barbut, Cl. (), „Le diagramme du treillis permutoèdre est intersection des diagrammes de deux produits directs d'ordres totaux”, Mathématiques, Informatique et Sciences Humaines, 112: 49–53 .
- en Postnikov, Alexander (), „Permutohedra, associahedra, and beyond”, International Mathematics Research Notices (6): 1026–1106, arXiv:math.CO/0507163
, doi:10.1093/imrn/rnn153, MR 2487491
- en Santmyer, Joe (), „For all possible distances look to the permutohedron”, Mathematics Magazine, 80 (2): 120–125, doi:10.1080/0025570X.2007.11953465
Legături externe
![]() | Portal Matematică |
- en Bryan Jacobs, Permutohedron la MathWorld.