Contele de Thatta-Coxeter | |
---|---|
Numit după |
William Tutt Harold Coxeter |
Vârfurile | treizeci |
coaste | 45 |
Diametru | patru |
Circumferinţă | opt |
Automorfisme | 1440 (Aut(S 6 )) |
Număr cromatic | 2 |
Indicele cromatic | 3 |
Proprietăți |
cubic
Celulă distanta-tranzitiva |
Graficul Tutt-Coxeter (de asemenea, Tutt 8-cell ) este un graf regulat cu 30 de vârfuri și 45 de muchii. Singurul cel mai mic grafic cubic cu circumferința 8 este celula și graficul Moore . Este bipartit și poate fi construit ca graficul Levi al unui patrulater generalizat W 2 (cunoscut sub numele de configurația Cremona-Richmond ). Numit după William Thomas Tutt și Harold Coxeter . Găsit de William Tutte ( Tutte 1947 ), dar relația sa cu combinația geometrică este explorată de ambii autori într-o pereche de lucrări comune ( Tutte, 1958 , Coxeter (a), 1958 ).
Este unul dintre cele treisprezece grafice de distanță cubică regulată [1] .
O construcție combinatorie deosebit de simplă a grafului Tutt-Coxeter a fost propusă de Coxeter ( Coxeter (b) 1958 ) și se bazează pe lucrările timpurii a lui D. D. Sylvester ( Sylvester 1844 ): formăm un set de șase elemente (de exemplu, acestea sunt literele a, b, c, d, e, f); Sylvester a definit doi ca fiind 15 perechi neordonate de elemente: ab, ac, ad, ae, af, bc, bd, be, bf, cd, ce, cf, de, df sau ef. El a mai definit mulţimi - împărţiri ale elementelor în trei două: (ab, cd, ef); (ab, ce, df); (ab, cf, de); (ac, bd, ef); (ac, fi, df); (ac, bf, de); (ad, bc, ef); (ad, fi, cf); (ad, bf, ce); (ae, bc, df); (ae, bd, cf); (ae, bf, cd); (af, bc, de); (af, bd, ce); (af, be, cd). Fiecare set conține 3 2s, iar fiecare 2 aparține a 3 seturi. Un grafic Tutta-Coxeter poate fi gândit ca un grafic în care fiecare vârf corespunde unui 2 și unui set de 2 - un vârf pentru fiecare set, iar muchiile conectează fiecare set la cei trei 2 pe care îi conține.
Pe baza acestei construcții, Coxeter a arătat că graficul Tutt-Coxeter este simetric . Are 1440 de automorfisme grafice , care pot fi identificate cu automorfisme ale grupului de permutare cu șase elemente ( Coxeter(b) 1958 ). Automorfismele interioare ale acestui grup corespund permutărilor a șase elemente din care definim morfeme și mulțimi. Aceste permutări acționează asupra grafului Tutte-Coxeter prin permutarea vârfurilor de pe fiecare parte a grafului bipartit, păstrând fiecare parte ca o mulțime. În plus, automorfismele exterioaregrupurile de permutare schimbă părțile unui graf bipartit. După cum a arătat Coxeter, orice cale de până la cinci muchii din graficul Tutt-Coxeter este echivalentă cu orice altă astfel de cale (adică sunt translate de la una la alta folosind unul dintre aceste automorfisme).
Numărul de intersecții ale graficului Tutt-Coxeter este 13.
Numărul cromatic al contelui Tutte-Coxeter este 2.
indicele cromatic al graficului Tutt-Coxeter este 3.