Rotationssystem

I kombinatorisk matematik kodar rotationssystem (även kallade kombinatoriska inbäddningar eller kombinatoriska kartor ) inbäddningar av grafer på orienterbara ytor genom att beskriva den cirkulära ordningen av en grafs kanter runt varje vertex. En mer formell definition av ett rotationssystem involverar par av permutationer ; ett sådant par är tillräckligt för att bestämma en multigraf , en yta och en 2-cellsinbäddning av multigrafen på ytan.

Varje rotationsschema definierar en unik 2-cellsinbäddning av en ansluten multigraf på en sluten orienterad yta (upp till orienteringsbevarande topologisk ekvivalens). Omvänt definierar varje inbäddning av en ansluten multigraf G på en orienterad sluten yta ett unikt rotationssystem med G som sin underliggande multigraf. Denna grundläggande likvärdighet mellan rotationssystem och 2-cells-inbäddningar avgjordes först i en dubbel form av Lothar Heffter på 1890-talet och användes flitigt av Ringel under 1950-talet. Oberoende Edmonds den ursprungliga formen av teoremet och detaljerna i hans studie har populariserats av Youngs. Generaliseringen till multigrafer presenterades av Gross och Alpert.

Rotationssystem är relaterade till, men inte samma sak som, rotationskartorna som används av Reingold et al. (2002) för att definiera sicksackprodukten av grafer. Ett rotationssystem anger en cirkulär ordning av kanterna runt varje vertex, medan en rotationskarta anger en (icke-cirkulär) permutation av kanterna vid varje vertex. Dessutom kan rotationssystem definieras för vilken graf som helst, medan som Reingold et al. definiera dem rotationskartor är begränsade till vanliga grafer .

Formell definition

Formellt definieras ett rotationssystem som ett par (σ, θ) där σ och θ är permutationer som verkar på samma jorduppsättning B , θ är en fixpunktsfri involution och gruppen <σ, θ> genererad av σ och θ verkar transitivt på B .

För att härleda ett rotationssystem från en 2-cellsinbäddning av en ansluten multigraf G på en orienterad yta, låt B bestå av pilarna (eller flaggorna eller halvkanterna ) av G ; det vill säga, för varje kant av G bildar vi två element av B , en för varje ändpunkt av kanten. Även när en kant har samma vertex som båda dess ändpunkter skapar vi två pilar för den kanten. Vi låter θ( b ) vara den andra pilen bildad från samma kant som b ; detta är helt klart en involution utan fasta punkter. Vi låter σ( b ) vara pilen i medurs position från b i den cykliska ordningen av kanter som faller in mot samma vertex, där "medurs" definieras av ytans orientering.

Om en multigraf är inbäddad på en orienterbar men inte orienterad yta, motsvarar den i allmänhet två rotationssystem, ett för var och en av ytans två orienteringar. Dessa två rotationssystem har samma involution θ, men permutationen σ för ett rotationssystem är inversen av motsvarande permutation för det andra rotationssystemet.

Återskapa inbäddningen från rotationssystemet

För att återställa en multigraf från ett rotationssystem bildar vi en vertex för varje bana av σ och en kant för varje bana av θ. En vertex är infallande med en kant om dessa två banor har en icke-tom skärningspunkt. Således är antalet incidenser per vertex storleken på omloppsbanan, och antalet incidenser per kant är exakt två. Om ett rotationssystem härleds från en 2-cellsinbäddning av en ansluten multigraf G , är grafen som härleds från rotationssystemet isomorf till G .

För att bädda in grafen som härrör från ett rotationssystem på en yta, bilda en skiva för varje bana av σθ och limma ihop två skivor längs kanten e närhelst de två pilarna som motsvarar e hör till de två banorna som motsvarar dessa skivor. Resultatet är en 2-cellsinbäddning av den härledda multigrafen, vars två celler är de skivor som motsvarar σθs banor. Ytan på denna inbäddning kan orienteras på ett sådant sätt att kanternas ordning medurs runt varje vertex är densamma som den medurs ordningen som ges av σ.

Karakterisera ytan på inbäddningen

Enligt Euler-formeln kan vi härleda släktet g för den slutna orienterbara ytan som definieras av rotationssystemet $(\sigma ,\theta )$ (det vill säga ytan på vilken den underliggande multigrafen är 2 -cell inbäddad). Lägg märke till att $V=|Z(\sigma )|$ , $E=|Z(\theta )|$ och $F=|Z(\sigma \theta )|$ . Det finner vi

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

där $Z(\phi )$ anger mängden permutationsbanor $\phi$ .

Se även

Kombinatorisk karta

Anteckningar

Cori, R.; Machì, A. (1992). "Kartor, hyperkartor och deras automorfismer: en undersökning". Expositiones Mathematicae . 10 : 403-467. MR 1190182 .
Edmonds, J. (1960). "En kombinatorisk representation för polyedriska ytor". Meddelanden från American Mathematical Society . 7 :646.
Edmonds, John Robert (1960). En kombinatorisk representation för orienterade polyedriska ytor (PDF) (Masters). University of Maryland. hdl : 1903/24820 .
Gross, JL; Alpert, SR (1974). "Den topologiska teorin om nuvarande grafer" . Journal of Combinatorial Theory, serie B . 17 (3): 218–233. doi : 10.1016/0095-8956(74)90028-8 . MR 0363971 .
Heffter, L. (1891). "Över das Problem der Nachbargebiete" . Matematiska Annalen . 38 (4): 477–508. doi : 10.1007/BF01203357 . S2CID 121206491 .
Heffter, L. (1898). "Über metacyklische Gruppen und Nachbarcontigurationen" . Matematiska Annalen . 50 (2–3): 261–268. doi : 10.1007/BF01448067 . S2CID 120691296 .
Lando, Sergei K.; Zvonkin, Alexander K. (2004). Grafer över ytor och deras tillämpningar . Encyclopaedia of Mathematical Sciences: Lower-Dimensional Topology II. Vol. 141. Springer-Verlag . ISBN 978-3-540-00203-1 . .
Mohar, Bojan ; Thomassen, Carsten (2001). Grafer på ytor . Johns Hopkins University Press. ISBN 0-8018-6689-8 .
Reingold, O.; Vadhan, S.; Wigderson, A. (2002). "Entropivågor, sicksack-grafprodukten och nya konstantgradersexpanderar". Annals of Mathematics . 155 (1): 157–187. arXiv : math/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 .
Youngs, JWT (1963). "Minimala inbäddningar och släktet för en graf" . Journal of Mathematics and Mechanics . 12 (2): 303–315. doi : 10.1512/iumj.1963.12.12021 . MR 0145512 .