Graf Möbiusa – Kantora

Graf Möbiusa – Kantora
Graf Möbiusa – Kantora
Nazwany po	August Ferdinand Möbius i S. Kantor
Wierzchołki	16
Krawędzie	24
Promień	4
Średnica	4
Obwód	6
Automorfizmy	96
Liczba chromatyczna	2
Indeks chromatyczny	3
Rodzaj	1
Grubość książki	3
Numer kolejki	2
Nieruchomości	; ; ; ; ; ; ; Symetryczna hamiltonowska dwudzielna jednostka sześcienna odległości Wykres Cayleya Doskonały Orientalnie prosty
	Tabela wykresów i parametrów

W matematycznej dziedzinie teorii grafów graf Möbiusa – Kantora jest symetrycznym dwudzielnym grafem sześciennym z 16 wierzchołkami i 24 krawędziami, nazwanymi na cześć Augusta Ferdinanda Möbiusa i Seligmanna Kantora . Można go zdefiniować jako uogólniony graf Petersena G (8,3): to znaczy tworzą go wierzchołki ośmiokąta , połączone z wierzchołkami ośmioramiennej gwiazdy, w której każdy punkt gwiazdy jest połączony z wskazuje trzy kroki od niego.

Konfiguracja Möbiusa-Kantora

Konfiguracja Möbiusa-Kantora.

Möbius (1828) zapytał, czy istnieje para wielokątów , z których każdy ma p boków, mających tę właściwość, że wierzchołki jednego wielokąta leżą na liniach przechodzących przez krawędzie drugiego wielokąta i odwrotnie. Jeśli tak, wierzchołki i krawędzie tych wielokątów utworzyłyby konfigurację rzutową . Dla p = 4 nie ma rozwiązania na płaszczyźnie euklidesowej , ale Kantor (1882) znalazł pary wielokątów tego typu, dla uogólnienia problemu, w którym punkty i krawędzie należą do zespolonej płaszczyzny rzutowej . Oznacza to, że w rozwiązaniu Kantora współrzędne wierzchołków wielokąta są liczbami zespolonymi . Rozwiązanie Kantora dla p = 4, pary wzajemnie wpisanych czworoboków w zespolonej płaszczyźnie rzutowej, nazywa się konfiguracją Möbiusa – Kantora . Graf Möbiusa – Kantora wywodzi swoją nazwę od bycia wykresem Levi w konfiguracji Möbiusa – Kantora. Ma jeden wierzchołek na punkt i jeden wierzchołek na potrójną, z krawędzią łączącą dwa wierzchołki, jeśli odpowiadają one punktowi i trójce, która zawiera ten punkt.

$elementami$ za pomocą grupy abelowej z dziewięcioma Ta grupa ma cztery podgrupy rzędu trzeciego (podzbiory elementów postaci ${\ Displaystyle (i, 0)}$ , ${\ Displaystyle (i, i)}$ , ${\ Displaystyle (i, 2i)}$ i ${\ Displaystyle (0, i)}$ odpowiednio), z których każdy może być użyty do podzielenia dziewięciu elementów grupowych na trzy zestawy po trzy elementy na zestaw. Tych dziewięć elementów i dwanaście cosetów tworzy konfigurację, konfigurację Hessego . Usunięcie elementu zerowego i czterech cosetów zawierających zero daje konfigurację Möbiusa – Kantora.

Jako podgraf

Wykres Möbiusa-Kantora jest podgrafem czterowymiarowego wykresu hipersześcianu , utworzonego przez usunięcie ośmiu krawędzi z hipersześcianu ( Coxeter 1950 ). Ponieważ hipersześcian jest wykresem jednostkowej odległości , wykres Möbiusa – Kantora można również narysować na płaszczyźnie ze wszystkimi krawędziami o jednostkowej długości, chociaż taki rysunek będzie koniecznie zawierał kilka par przecinających się krawędzi.

Wykres Möbiusa – Kantora występuje również wiele razy, podobnie jak w indukowanym podgrafie wykresu Hoffmana – Singletona . Każdy z tych przypadków jest w rzeczywistości wektorem własnym wykresu Hoffmana-Singletona z powiązaną wartością własną -3. Każdy wierzchołek, który nie znajduje się na indukowanym grafie Möbiusa – Kantora, sąsiaduje dokładnie z czterema wierzchołkami na grafie Möbiusa – Kantora, po dwa w połowie dwupodziału grafu Möbiusa – Kantora.

Topologia

Wykres Möbiusa – Kantora osadzony na torusie. Krawędzie rozciągające się w górę od centralnego kwadratu należy postrzegać jako łączące się z odpowiednią krawędzią rozciągającą się w dół od kwadratu, a krawędzie rozciągające się w lewo od kwadratu należy postrzegać jako łączące się z odpowiednią krawędzią rozciągającą się w prawo.

Grafu Möbiusa – Kantora nie można osadzić bez przecięć na płaszczyźnie; ma numer przecięcia 4 i jest najmniejszym wykresem sześciennym z tym numerem przecięcia (sekwencja A110507 w OEIS ). Dodatkowo podaje przykład wykresu, którego wszystkie numery przecięć podgrafów różnią się od niego o dwa lub więcej. Jest to jednak graf toroidalny : ma osadzenie w torusie , w którym wszystkie ściany są sześciokątami ( Marušič & Pisanski 2000 ). Podwójny wykres tego osadzania to graf hiperoktaedryczny K _2,2,2,2 .

Istnieje jeszcze bardziej symetryczne osadzenie wykresu Möbiusa – Kantora w podwójnym torusie , który jest regularną mapą , z sześcioma ośmiokątnymi ścianami, w którym wszystkie 96 symetrii wykresu można zrealizować jako symetrie osadzania; Coxeter (1950) przypisuje to osadzenie Threlfall (1932) . Jego 96-elementowa grupa symetrii ma wykres Cayleya , który sam może być osadzony na podwójnym torusie i został pokazany przez Tuckera (1984) jako wyjątkowa grupa z rodzajem dwa. Graf Cayleya na 96 wierzchołkach jest grafem flagowym regularnej mapy rodzaju 2, której szkieletem jest graf Möbiusa – Kantora. Oznacza to, że można go uzyskać ze zwykłej mapy jako szkielet podwójnego podziału barycentrycznego. Rzeźba DeWitta Godfreya i Duane'a Martineza przedstawiająca podwójny torus osadzony w symetrii wykresu Möbiusa-Kantora została odsłonięta w Muzeum Techniki Słowenii w ramach 6. Słoweńskiej Międzynarodowej Konferencji Teorii Grafów w 2007 roku. W 2013 roku obracająca się wersja rzeźba została odsłonięta na Uniwersytecie Colgate .

Wykres Möbiusa – Kantora dopuszcza osadzenie w potrójnym torusie (torus rodzaju 3), który jest regularną mapą mającą cztery 12-kątne ściany i jest podwójnym osadzeniem podwójnego torusa Petriego opisanym powyżej; ( Marušič & Pisanski 2000 ).

Lijnen i Ceulemans (2004) , motywowani badaniem potencjalnych struktur chemicznych związków węgla, badali rodzinę wszystkich zanurzeń grafu Möbiusa-Kantora na 2- rozmaitościach ; wykazali, że istnieje 759 nierównoważnych osadzeń.

Właściwości algebraiczne

Grupa automorfizmu grafu Möbiusa – Kantora jest grupą rzędu 96. Działa przechodnie na wierzchołkach, krawędziach i łukach grafu. Dlatego graf Möbiusa – Kantora jest grafem symetrycznym . Ma automorfizmy, które przenoszą dowolny wierzchołek do dowolnego innego wierzchołka i dowolną krawędź do dowolnej innej krawędzi. Według spisu Fostera graf Möbiusa – Kantora jest unikalnym sześciennym grafem symetrycznym z 16 wierzchołkami i najmniejszym sześciennym grafem symetrycznym, który nie jest również przechodni na odległość . Wykres Möbiusa-Kantora jest również wykresem Cayleya .

Uogólniony graf Petersena G ( n, k ) jest przechodni przez wierzchołki wtedy i tylko wtedy, gdy n = 10 i k = 2 lub gdy k ² ≡ ±1 (mod n ) i jest przechodni przez krawędzie tylko w następujących siedmiu przypadkach: ( n ,k ) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5) lub (24,5) ( Frucht, Graver i Watkinsa 1971 ). Tak więc wykres Möbiusa – Kantora jest jednym z zaledwie siedmiu symetrycznych uogólnionych grafów Petersena. Jego symetryczne osadzenie podwójnego torusa jest odpowiednio jedną z zaledwie siedmiu regularnych map sześciennych, w których całkowita liczba wierzchołków jest dwukrotnie większa niż liczba wierzchołków na ścianę ( McMullen 1992 ). $Displaystyle$ siedmiu symetrycznych uogólnionych grafów Petersena znajduje się $G (5,2$ , wykres Petersena , sol wykres dwunastościenny ${\ Displaystyle G (10,2)}$ , wykres Desarguesa ${\ Displaystyle G (10,3)}$ i wykres Nauru ${\ styl wyświetlania G(12,5)}$ .