Flag graphs and symmetry type graphs : doctoral thesis

Río Francos, María del (author), Pisanski, Tomaž (mentor), Hubard, Isabel (comentor)

A map, as a 2-cell embedding of a graph on a closed surface, is called a ▫$k$▫-orbit map if the group of automorphisms (or symmetries) of the map partitions its set of flags into ▫$k$▫ orbits. In 2012, Steve Wilson introduced the concept of maniplex, aming to unify the notion of maps and abstract polytopes. In particular, maniplexes generalise maps on surfaces to higher ranks. The combinatorial structure of a maniplex of rank ▫$(n-1)$▫ (or an ▫$(n-1)$▫-maniplex) is completely determined by an edge-coloured ▫$n$▫-valent graph with chromatic index ▫$n$▫, with ▫$n \ge 1$▫, often called the flag graph of the maniplex. Maps will be regarded as maniplexes of rank 2 (or 2-maniplexes), and defined as Lins and Vince studied the combinatorial maps since 1982-1983. Thus, similarly to maps, a ▫$k$▫-orbit maniplex is one that has ▫$k$▫ orbits of flags under the action of its automorphism group. In the first part of this thesis we introduce the notion of symmetry type graphs of maniplexes and make use of them to study ▫$k$▫-orbit maniplexes, as well as fully-transitive 3-maniplexes. We classify all possible symmetry types of ▫$k$▫-orbit 2-maniplexes for ▫$k \le 5$▫, as well as all self-dual, properly and improperly, ▫$k$▫-orbit maps with ▫$k \le 7$▫. Moreover, we show that there are no fully-transitive ▫$k$▫-orbit 3-maniplexes with ▫$k > 1$▫ an odd number, we classify 3-orbit maniplexes and determine all face transitivities for 3- and 4-orbit maniplexes. Furthermore, we give generators of the automorphism group of a maniplex, given its symmetry typegraph. The second part of this work is motivated by the classification for ▫$k$▫-orbit, up to ▫$k \le 4$▫, that Orbanić, Pellicer and Weiss gave. Thus, motivated by their results, we use symmetry type graphs to extend such study and classify all the types of ▫$k$▫-orbit maps with the same operations on maps, up to ▫$k \le 6$▫. Furthermore, we studied other operations on maps, such as the chamfering and leapfrog operations. In particular, we determine all possible symmetry types of maps that result from other maps after applying the chamfering operation and give the number of possible flag-orbits that has the chamfering map of a ▫$k$▫-orbit map.

• Language: English
• Keywords: flag graph, symmetry type graph, k-orbit map, maniplex, medial, chamfering, truncation, leapfrog
• Work type: Doctoral dissertation
• Typology: 2.08 - Doctoral Dissertation
• Organization: FMF - Faculty of Mathematics and Physics
• Place of publishing: Ljubljana
• Publisher: [M. del Río Francos]
• Year: 2014
• Number of pages: VII, 141 str.
• PID: 20.500.12556/RUL-95851
• UDC: 514.172.4:519.17(043.3)
• COBISS.SI-ID: 16858201
• Publication date in RUL: 24.10.2017

Secondary language

• Language: Slovenian
• Title: Praporni grafi in grafi simetrijskih tipov

Abstract

Zemljevid (t.j. celična vložitev grafa na sklenjeno ploskev) imenujemo ▫$k$▫-orbitni zemljevid, če grupa avtomorfizmov (oz. simetrij) zemljevida razdeli njegovo množico praporov v ▫$k$▫ orbit. Pred kratkim (2012) je Steve Wilson, v želji da poenoti pojma zemljevidov in abstraktnih politopov, vpeljal t.i. maniplekse. Manipleksi predstavljajo posplošitev zemljevidov na objekte višjih dimenzij oziroma rangov. Kombinatorična struktura manipleksa ranga ▫$(n-1)$▫ (ali ▫$(n-1)$▫-manipleksa) je popolnoma določena s po povezavah pobarvanim ▫$n$▫-valentnim grafom (s kromatičnim številom ▫$n \ge 1$▫), t.i. prapornim grafom manipleksa. Zemljevide obravnavamo kot maniplekse ranga 2 (oz. 2-maniplekse) in jih definiramo v skladu z raziskavami kombinatoričnih zemljevidov Linsa in Vincea v letih 1982-1983. Tako je, podobno kot pri zemljevidih, ▫$k$▫-orbitni manipleks definiran kot manipleks, ki ima ▫$k$▫ prapornih orbit glede na delovanje njegove grupe avtomorfizmov. V prvem delu disertacije vpeljemo pojem simetrijskega grafa manipleksa in uporabimo simetrijske grafe pri obravnavi ▫$k$▫-orbitnih manipleksov ter polno tranzitivnih 3-manipleksov. Klasificiramo vse možne simetrijske tipe ▫$k$▫-orbitnih manipleksov za ▫$k \le 5$▫, pa tudi vseh pravih in nepravih samodualov ▫$k$▫-orbitnih zemljevidov za ▫$k \le 7$▫. Pokažemo, da za nobeno liho število ▫$k > 1$▫ ne obstaja polno tranzitiven ▫$k$▫-orbitni 3-manipleks, klasificiramo 3-orbitne maniplekse in določimo vse tranzitivne avtomorfizme lic 3- in 4-orbitnih manipleksov. Predstavimo tudi generatorje grupe avtomorfizmov manipleksa, ki utreza danemu simetrijskemu grafu. Orbanić, Pellicer in Weiss so klasificirali ▫$k$▫-orbitne zemljevide za vrednosti ▫$k \le 4$▫ s pomočjo operacij na zemljevidih, npr. z operacijama sredinjenja (angl. medial) in prisekanja (angl. truncation). V drugem delu disertacije na podlagi teh rezultatov uporabimo simetrijske grafe za razširitev takšnih raziskav in klasificiramo vse tipe ▫$k$▫-orbitnih zemljevidov z istima operacijama na zemljevidih za vrednosti ▫$k \le 6$▫. Raziščemo tudi druge operacije na zemljevidih, kot sta npr. operaciji brušenja (angl. chamfering) in preskoka (angl. leapfrog). Določimo tudi vse možne simetrijske tipe zemljevidov, ki jih dobimo iz drugih zemljevidov z operacijama brušenja, in raziščemo, koliko prapornih orbit lahko ima brušeni zemljevid ▫$k$▫-orbitnega zemljevida.

• Keywords: graf praporov, simetrijski graf, k-orbitni zemljevid, manipleks, sredinjenje, brušenje, prisekanje, preskok