Permutoedru

Permutoedrul de ordinul 4

În matematică permutoedrul de ordinul n este un politop (Format:Mvar−1)-dimensional conținut într-un spațiu Format:Mvar-dimensional. Coordonatele vârfurilor sale (vârfuri etichetate în imaginea din dreapta) sunt permutări ale primelor Format:Mvar 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, permutoedrele au fost studiate pentru prima dată de Pieter Hendrik Schoute. Numele de permutoèdre a fost inventat de Georges Guilbaud și Pierre Rosenstiehl. Ei descriu cuvântul drept un barbarism, dar ușor de reținut și îl supun criticii cititorilor lor.

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 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

Format:Color, Format:Color, fațete, Format:Color Dimensiunea feței Format:Math.

Format:Color Format:Color Format:Color Format:Color Format:Color Format:Color Format:Color Format:Color Format:Color Format:Color 1 Format:Color Format:Color Format:Color Format:Color 1 14 Format:Color Format:Color Format:Color Format:Color 1 30 150 Format:Color Format:Color Format:Color

Permutoedrul de ordinul Format:Mvar are Format:Math vârfuri, fiecare fiind adiacent altor Format:Math. Numărul laturilor este Format:Math, iar lungimea lor este $\sqrt{2}$.

Două vârfuri conectate diferă prin interschimbarea a două coordonate, ale căror valori diferă cu 1. Perechea de locuri interschimbate corespunde direcției laturii. (În imaginea de la începutul articolului vârfurile Format:Math și Format:Math 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 Format:Math, deoarece acestea corespund unor submulțimi proprii nevide Format:Math din Format:Math Vârfurile unei fațete corespunzătoare submulțimii Format:Math au în comun faptul că coordonatele lor pe locurile din Format:Math sunt mai mici decât coordonatele din pozițiile care nu sunt în S.

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 Format:Math unde Format:Math sunt marcate cu un fundal întunecat. Se observă că sunt mai mici decât restul. Pătratul de deasupra corespunde submulțimii Format:Math Î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 Format:Math (permutoedrul însuși) corespund ordonării slabe stricte a mulțimii Format:Math Deci numărul tuturor fețelor este al Format:Math-lea număr ordonat Bell. O față de dimensiunea Format:Math corespunde unei ordonări cu clasa de echivalență Format:Math.

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ă Format:Math. 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 Format:Math atribuită fațetei, deci ordonarea este Format:Math. Imaginile de mai jos arată cum fațetele permutoedrului Format:Math corespund proiecției simpliciale a unui [[hipercub|Format:Mvar-cub]]. Etichetele de coordonate binare corespund submulțimilor Format:Math, de ex. 0011 la Format:Math (Vârful proiectat spre centru nu corespunde unei fațete. Nici vârful său opus în Format:Mvar-cub, care nu face parte din proiecție.)

Numărul de fețe de dimensiunea Format:Math în permutoedrul de ordin Format:Math este dat de triunghiul Format:Math:

$T(n,k)=k!\cdot \left\{\genfrac{}{}{0ex}{}{n}{k}\right\}$

cu $\left\{\genfrac{}{}{0ex}{}{n}{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: Format:Ill-wd S_n acționează asupra permutoedrului prin permutarea coordonatelor.

Permutoedrul este un zonotop; o copie translată a permutoedrului poate fi generată ca Format:Ill-wd a unui număr triunghiular Format:Math de segmente care conecteaă perechile de vectori ai bazei standard.Format:Sfnp

Vârfurile și laturile permutoedrului sunt izomorfe cu unul dintre Format:Ill-wd ale grupului simetric, și anume cel Format:Ill-wd prin transpoziții care schimbă elemente consecutive. Vârfurile grafului Cayley sunt permutările inverse ale celor din permutoedru. Imaginea din dreapta arată graful Cayley al lui S4. Culorile laturilor sale reprezintă cele 3 transpoziții generatoare: Format:Color, Format:Color, Format:Color.

Acest graf Cayley este un ciclu Hamiltonian. Un asemenea ciclu poate fi găsit prin algoritmul Steinhaus–Johnson–Trotter.

Teselarea spațiului

Format:Imagine multiplă 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 Format:Ill-wd pentru $A_{n-1}^{*}$. Această latice este uneori numită latice permutoedrică.Format:Sfnp

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

Bibliografie

• Format:En icon Format:Citation
• Format:En icon Format:Citation.
• Format:En icon Format:Citation.

Lectură suplimentară

• Format:En icon Format:Citation.
• Format:En icon Format:Citation
• Format:En icon Format:Citation

Legături externe

• Format:En icon Format:Mathworld