Page 332 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 332
SYMMETRY OF GRAPHS, MAPS AND POLYTOPES (MS-9)
Some observations about regular maps
Marston Conder, m.conder@auckland.ac.nz
University of Auckland, New Zealand
A map on an orientable surface is called ‘orientably-regular’ if its automorphism group has
a single orbit on arcs (incident vertex-edge pairs), and is then called ‘reflexible’ or ‘chiral’
depending on whether or not it admits reflections (for example, fixing an arc but swapping the
two faces incident with it). In every such map with a high degree of symmetry, all vertices have
the same valency, say k, and all faces have the same size, say m, and then the (ordered) pair
{m, k} is called the ‘type’ of the map.
Writing a book with Gareth Jones, Jozef Širánˇ and Tom Tucker) on regular maps has
prompted us to review and extend what is known about them. Various questions have arisen
naturally, including what I believe is the most important unanswered one, namely whether chi-
rality is more prevalent than reflexibility. Other questions include these: What types {m, k}
occur the most frequently among orientably-regular maps on hyperbolic surfaces? What kinds
of groups are the most prevalent as the group of orientation-preserving automorphisms? (Sim-
ple groups? insoluble groups? soluble groups? 2-groups?) Is chirality is more prevalent than
reflexibility for a given type? I will give some partial answers to these questions, with reference
to computational evidence. These answers may be surprising.
On the Asymmetrizing Cost and Density of Graphs
Wilfried Imrich, wilfried.imrich@unileoben.ac.at
Montanuniversität Leoben, Austria
Coauthors: Thomas Lachmann, Thomas W. Tucker, Gundelinde M. Wiegel
A set S of vertices in a graph G with nontrivial automorphism group is asymmetrizing if the
identity mapping is the only automorphism of G that preserves S as a set. If such sets exist,
then their minimum cardinality is the asymmetrizing cost ρ(G) of G. For finite graphs the
asymmetrizing density δ(G) of G is the quotient of the size of S by the order of G. For infinite
graphs δ(G) is defined by a limit process.
The talk discusses bounds on the asymmetrizing cost, classes of graphs with asymmetrizing
density zero, and infinite graphs with finite asymmetrizing cost.
It is easy to construct graphs with positive asymmetrizing density, unless they are vertex
transitive. Hitherto no infinite vertex transitive graphs with δ(G) > 0 seem to have been known.
Here we construct connected, infinite vertex transitive cubic graphs of asymmetrizing density
δ(G) = n−12−n−1 for each n ≥ 1.
We also construct finite vertex transitive cubic graphs of arbitrarily large asymmetrizing
cost. The examples are Split Praeger–Xu graphs, for which we provide another characterization.
330
Some observations about regular maps
Marston Conder, m.conder@auckland.ac.nz
University of Auckland, New Zealand
A map on an orientable surface is called ‘orientably-regular’ if its automorphism group has
a single orbit on arcs (incident vertex-edge pairs), and is then called ‘reflexible’ or ‘chiral’
depending on whether or not it admits reflections (for example, fixing an arc but swapping the
two faces incident with it). In every such map with a high degree of symmetry, all vertices have
the same valency, say k, and all faces have the same size, say m, and then the (ordered) pair
{m, k} is called the ‘type’ of the map.
Writing a book with Gareth Jones, Jozef Širánˇ and Tom Tucker) on regular maps has
prompted us to review and extend what is known about them. Various questions have arisen
naturally, including what I believe is the most important unanswered one, namely whether chi-
rality is more prevalent than reflexibility. Other questions include these: What types {m, k}
occur the most frequently among orientably-regular maps on hyperbolic surfaces? What kinds
of groups are the most prevalent as the group of orientation-preserving automorphisms? (Sim-
ple groups? insoluble groups? soluble groups? 2-groups?) Is chirality is more prevalent than
reflexibility for a given type? I will give some partial answers to these questions, with reference
to computational evidence. These answers may be surprising.
On the Asymmetrizing Cost and Density of Graphs
Wilfried Imrich, wilfried.imrich@unileoben.ac.at
Montanuniversität Leoben, Austria
Coauthors: Thomas Lachmann, Thomas W. Tucker, Gundelinde M. Wiegel
A set S of vertices in a graph G with nontrivial automorphism group is asymmetrizing if the
identity mapping is the only automorphism of G that preserves S as a set. If such sets exist,
then their minimum cardinality is the asymmetrizing cost ρ(G) of G. For finite graphs the
asymmetrizing density δ(G) of G is the quotient of the size of S by the order of G. For infinite
graphs δ(G) is defined by a limit process.
The talk discusses bounds on the asymmetrizing cost, classes of graphs with asymmetrizing
density zero, and infinite graphs with finite asymmetrizing cost.
It is easy to construct graphs with positive asymmetrizing density, unless they are vertex
transitive. Hitherto no infinite vertex transitive graphs with δ(G) > 0 seem to have been known.
Here we construct connected, infinite vertex transitive cubic graphs of asymmetrizing density
δ(G) = n−12−n−1 for each n ≥ 1.
We also construct finite vertex transitive cubic graphs of arbitrarily large asymmetrizing
cost. The examples are Split Praeger–Xu graphs, for which we provide another characterization.
330
