Permutoedru

Î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 ${\sqrt {2}}$ .

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 $2 n - 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. Coordonatele de pe locurile $i$ unde $i \in S$ sunt marcate cu un fundal întunecat. Se observă că sunt mai mici decât restul. Pătratul de deasupra corespunde submulțimii ${3, 4}.$ În cele patru vârfuri ale sale, coordonatele de pe ultimele două locuri au cele mai mici valori (și anume 1 și 2).
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).
Fiecare centru al unei fețe este etichetat cu o ordine slabă strictă. De exemplu. pătratul de deasupra ca 3 4 | 1 2, care reprezintă $({3, 4}, {1, 2})$ .
Ordonările sunt ordonate parțial prin rafinare, cele mai fine fiind la exterior.
Deplasarea de-a lungul unei laturi spre interior înseamnă fuzionarea a două clase de echivalență învecinate.

Etichetele vârfurilor a | b | c | d interpretate drept permutări (a, b, c, d) sunt cele care formează graful Cayley.

Fațete printre fețe
Fațetele menționate mai sus se numără printre aceste fețe și corespund ordonărilor cu două clase de echivalență. Primul este folosit ca submulțimea $S$ atribuită fațetei, deci ordonarea este $(S, S c)$ . Imaginile de mai jos arată cum fațetele permutoedrului $n$ corespund proiecției simpliciale a unui $n$ -cub. Etichetele de coordonate binare corespund submulțimilor $S$ , de ex. 0011 la ${3, 4}.$ (Vârful proiectat spre centru nu corespunde unei fațete. Nici vârful său opus în $n$ -cub, care nu face parte din proiecție.)

Numărul de fețe de dimensiunea $d = n - k$ în permutoedrul de ordin $n$ este dat de triunghiul $T$ :^[9]

T(n,k)=k!\cdot \left\{{n \atop k}\right\}

cu $\textstyle \left\{{n \atop k}\right\}$ 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

Graful Cayley S₄ ca permutoedru

Permutoedrul este tranzitiv pe vârfuri: grupul simetric^⁠(d) S_n 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

Teselarea spațiului cu permutoedre de ordinul 3 și 4

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:

x₁ + x₂ + ... + x_n = 0

x₁ ≡ x₂ ≡ ... ≡ x_n (mod n).

Aceaste este laticea $A_{n-1}^{*}$ , laticea duală a laticei $A_{n-1}$ . În alte cuvinte, permutoedrul este celula Voronoi^⁠(d) pentru $A_{n-1}^{*}$ . 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 R⁴ 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. (1995), Lectures on Polytopes, Springer-Verlag, Graduate Texts in Mathematics 152
^ en Schoute, Pieter Hendrik (1911), „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 (1963), „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 (1972), „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 (2013), „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. (1977), „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 (2018), Compact extended linear programming models, Cham, Switzerland: Springer, ISBN 978-3-319-63975-8 .

Lectură suplimentară

en Le Conte de Poly-Barbut, Cl. (1990), „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 (2009), „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 (2007), „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.

[1] Ziegler, Günter M. (1995), Lectures on Polytopes, Springer-Verlag, Graduate Texts in Mathematics 152

[2] Schoute, Pieter Hendrik (1911), „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

[3] r Guilbaud, Georges Th.; Rosenstiehl, Pierre (1963), „Analyse algébrique d'un scrutin”, Mathématiques et Sciences Humaines, 4: 9–33

[4] În original în franceză le mot permutoèdre est barbare, mais il est facile à retenir; soumettons-le aux critiques des lecteurs.

[5] Bowman, V. Joseph (1972), „Permutation polyhedra”, SIAM Journal on Applied Mathematics, 22 (4): 580–589, doi:10.1137/0122054, JSTOR 2099695, MR 0305800

[6] Gaiha & Gupta (1977).

[7] Lancia (2018), p. 105 (see chapter The Permutahedron).

[zface-8] v. de exemplu Ziegler (1995), p. 18.

[9] Șirul A019538 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)

[FOOTNOTEZiegler1995200-10] Ziegler (1995), p. 200.

[11] Această etichetare a grafului Cayley este prezentată, de exemplu, de Ziegler (1995)

[FOOTNOTEBaekAdamsDolson2013-12] Baek, Adams & Dolson (2013).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]