Układ rotacyjny

W matematyce kombinatorycznej systemy rotacji (zwane również osadzaniami kombinatorycznymi lub mapami kombinatorycznymi ) kodują osadzenie grafów na orientowalnych powierzchniach , opisując kołowe uporządkowanie krawędzi grafu wokół każdego wierzchołka . Bardziej formalna definicja systemu rotacji obejmuje pary permutacji ; taka para jest wystarczająca do wyznaczenia multigrafu , powierzchni i osadzania 2 komórek multigrafu na powierzchnię.

Każdy schemat rotacji definiuje unikalne 2-komórkowe osadzenie połączonego multigrafu na zamkniętej zorientowanej powierzchni (aż do równoważności topologicznej zachowującej orientację). I odwrotnie, każde osadzenie połączonego multigrafu G na zorientowanej zamkniętej powierzchni definiuje unikalny system rotacji, w którym G jest podstawowym multigrafem. Ta podstawowa równoważność między systemami rotacyjnymi a osadzeniem 2-komórkowym została po raz pierwszy ustalona w podwójnej formie przez Lothara Hefftera w latach 90. XIX wieku i szeroko stosowana przez Ringela w latach pięćdziesiątych. Niezależnie, Edmonds dał pierwotną postać twierdzenia, a szczegóły jego badań zostały spopularyzowane przez Youngsa. Uogólnienie na multigrafy przedstawili Gross i Alpert.

Systemy rotacji są spokrewnione, ale nie tożsame z mapami rotacji używanymi przez Reingolda i in. (2002), aby zdefiniować iloczyn zygzakowaty grafów. System rotacji określa kołowe uporządkowanie krawędzi wokół każdego wierzchołka, podczas gdy mapa rotacji określa (niekołową) permutację krawędzi w każdym wierzchołku. Ponadto systemy rotacji można zdefiniować dla dowolnego wykresu, podczas gdy jak Reingold i in. zdefiniuj je mapy rotacji są ograniczone do zwykłych wykresów .

Definicja formalna

Formalnie system rotacyjny definiuje się jako parę (σ, θ), gdzie σ i θ są permutacjami działającymi na tym samym zbiorze podstawowym B , θ jest inwolucją wolną od punktów stałych , a grupa <σ, θ> generowana przez σ a θ działa przechodnio na B .

Aby wyprowadzić system rotacji z 2-komórkowego osadzania połączonego multigrafu G na zorientowanej powierzchni, niech B składa się z rzutek (lub flag lub półkrawędzi ) G ; to znaczy dla każdej krawędzi G tworzymy dwa elementy B , po jednym dla każdego punktu końcowego krawędzi. Nawet jeśli krawędź ma ten sam wierzchołek co oba jej punkty końcowe, tworzymy dwie rzutki dla tej krawędzi. Niech θ( b ) będzie drugą strzałką utworzoną z tej samej krawędzi co b ; jest to wyraźnie inwolucja bez punktów stałych. Niech σ( b ) będzie strzałką w pozycji zgodnej z ruchem wskazówek zegara od b w cyklicznym porządku krawędzi padających na ten sam wierzchołek, gdzie „zgodnie z ruchem wskazówek zegara” jest określone przez orientację powierzchni.

Jeśli multigraf jest osadzony na orientowalnej, ale nie zorientowanej powierzchni, generalnie odpowiada dwóm systemom rotacji, po jednym dla każdej z dwóch orientacji powierzchni. Te dwa systemy rotacji mają tę samą inwolucję θ, ale permutacja σ dla jednego systemu rotacji jest odwrotnością odpowiedniej permutacji dla drugiego systemu rotacji.

Odzyskanie osadzania z systemu rotacyjnego

Aby odzyskać multigraf z układu rotacyjnego, tworzymy wierzchołek dla każdej orbity σ i krawędź dla każdej orbity θ. Wierzchołek jest incydentny z krawędzią, jeśli te dwie orbity mają niepuste przecięcie. Zatem liczba przypadków na wierzchołek jest wielkością orbity, a liczba przypadków na krawędź wynosi dokładnie dwa. Jeśli system rotacji pochodzi z 2-komórkowego osadzania połączonego multigrafu G , wykres wyprowadzony z systemu rotacji jest izomorficzny z G .

Aby osadzić wykres pochodzący z układu rotacyjnego na powierzchni, uformuj dysk dla każdej orbity σθ i sklej dwa dyski wzdłuż krawędzi e, ilekroć dwie strzałki odpowiadające e należą do dwóch orbit odpowiadających tym dyskom. Rezultatem jest 2-komórkowe osadzenie wyprowadzonego multigrafu, którego dwie komórki są dyskami odpowiadającymi orbitom σθ. Powierzchnia tego osadzania może być zorientowana w taki sposób, że uporządkowanie krawędzi wokół każdego wierzchołka zgodnie z ruchem wskazówek zegara jest takie samo, jak uporządkowanie zgodne z ruchem wskazówek zegara określone przez σ.

Charakterystyka powierzchni osadzania

Zgodnie ze $($ możemy wywnioskować rodzaj g zamkniętej orientowalnej powierzchni określonej przez system rotacji to znaczy powierzchnię, na której bazowy multigraf wynosi -osadzone w komórce). Zauważ, że ${\ Displaystyle V = | Z (\ sigma) |}$ , ${\ Displaystyle E = | Z (\ teta) |}$ i ${\ Displaystyle F = | Z (\ sigma \ teta) |}$ . Znaleźliśmy to

{\ Displaystyle g = 1- {\ frac {1}{2}}(V-E+F)=1-{\frac {1}{2}}(|Z(\sigma )|-|Z(\theta )|+|Z(\sigma \theta )|)}

gdzie $φ$ zbiór orbit permutacji $Displaystyle \$ .

Zobacz też

Mapa kombinatoryczna

Notatki

Cori, R.; Machi, A. (1992). „Mapy, hipermapy i ich automorfizmy: ankieta”. Expositiones Mathematicae . 10 : 403–467. MR 1190182 .
Edmonds, J. (1960). „Kombinatoryczna reprezentacja powierzchni wielościennych”. Zawiadomienia Amerykańskiego Towarzystwa Matematycznego . 7 : 646.
Edmonds, John Robert (1960). Kombinatoryczna reprezentacja zorientowanych powierzchni wielościennych (PDF) (Masters). Uniwersytet Marylandu. hdl : 1903/24820 .
Gross, JL; Alpert, SR (1974). „Topologiczna teoria grafów prądu” . Dziennik teorii kombinatorycznej, seria B. 17 (3): 218–233. doi : 10.1016/0095-8956(74)90028-8 . MR 0363971 .
Heffter, L. (1891). „Über das Problem der Nachbargebiete” . Mathematische Annalen . 38 (4): 477–508. doi : 10.1007/BF01203357 . S2CID 121206491 .
Heffter, L. (1898). "Über metacyklische Gruppen und Nachbarcontigurationen" . Mathematische Annalen . 50 (2–3): 261–268. doi : 10.1007/BF01448067 . S2CID 120691296 .
Lando, Siergiej K.; Zvonkin, Aleksander K. (2004). Wykresy na powierzchniach i ich zastosowaniach . Encyklopedia nauk matematycznych: topologia dolnowymiarowa II . Tom. 141. Springer-Verlag . ISBN 978-3-540-00203-1 . .
Mohar, Bojan ; Thomassen, Carsten (2001). Wykresy na powierzchniach . Wydawnictwo Uniwersytetu Johnsa Hopkinsa. ISBN 0-8018-6689-8 .
Reingold, O.; Vadhan, S.; Wigderson, A. (2002). „Fale entropii, iloczyn wykresu zygzakowatego i nowe ekspandery o stałym stopniu”. Roczniki matematyki . 155 (1): 157–187. arXiv : matematyka/0406038 . doi : 10.2307/3062153 . JSTOR 3062153 . MR 1888797 . S2CID 120739405 .
Ringel, G. (1965). „Das Geschlecht des vollständigen paaren Graphen”. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg . 28 (3–4): 139–150. doi : 10.1007/BF02993245 . MR 0189012 . S2CID 120414651 .
Młodzi, JWT (1963). „Minimalne osadzenie i rodzaj wykresu” . Dziennik matematyki i mechaniki . 12 (2): 303–315. doi : 10.1512/iumj.1963.12.12021 . MR 0145512 .