8
$\begingroup$

A vertex-edge flag in a graph is a vertex together with an edge incident to that vertex. Given a graph $\Gamma$ embedded in a compact oriented surface $S$, when does the group of homeomorphisms of $S$ act transitively on vertex-edge flags of $\Gamma$?

We can start by looking a graphs embedded in the sphere, and start among those by looking at graphs that consist of the vertices and edges of a convex polyhedron. Among these, the obvious examples on which isometries act transitively on vertex-edge flags are the 5 Platonic solids. However, there are also two Archimedean solids with this property, namely the cuboctahedron:

cuboctahedron

and the icosidodecahedron:

enter image description here

I believe these are all the convex polyhedra on which isometries act transitively on vertex-edge flags. A polyhedron is said to be isotoxal if isometries act transitively on edges. There are 9 isotoxal convex polyhedra, and among these I see 7 on which isometries act transtively on vertex-edge flags: the 5 Platonic solids and the 2 shown above.

There are also infinitely many other connected graphs embedded in the sphere on which isometries act transitively on vertex-edge flags, namely the hosohedra, like this:

enter image description here

and the dihedra, like this:

enter image description here

I believe these are all the connected graphs embedded in the sphere on which isometries acts transitively on vertex-edge flags. If we consider graphs embedded in the sphere that are not connected, we get a host of other examples: for example, a bunch of equal-sized regular $n$-gons embedded in the sphere. If we further drop the requirement that the homeomorphisms be isometries, we get even more examples: for example, a bunch of copies of the complete graph on 4 vertices embedded in the sphere. I am happy to restrict attention to connected graphs, to avoid such clutter.

I am also happy to omit graphs that have self-loops.

So, here is a sub-question that interests me: what are all the connected graphs without self-loops embedded in the sphere on which homeomorphisms of the sphere act transitively on vertex-edge flags? Have I listed them all, or are there more?

(Whoops, here are some more: the empty graph, the graph with one vertex and no edges, and the graph with two vertices and one edge connecting them. The last might be considered a degenerate hosohedron.)

When we go to higher genus the situation becomes a lot more complicated and interesting. For example, in genus 3 we have Klein's quartic curve tiled by 56 triangles meeting 7 at each vertex:

enter image description here

So, I'd be perfectly happy to hear classifications that only handle surfaces of genus less than some fixed value.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ A very common term for a vertex-edge flag is an arc. Let me use this for simplicity. You are asking about maps with an arc-transitive group of automorphisms. It's not hard to see that the maximal amount of symmetry a map can have is to be arc-transitive with the arc-stabiliser having order $2$. This is the so-called "regular" case that Noam mentioned. In that case, the vertex-stabiliser is dihedral, of order $2k$, where $k$ is the valency. $\endgroup$
    – verret
    Commented Apr 29, 2016 at 20:42
  • 1
    $\begingroup$ The only other option is that the arc-stabiliser is trivial and hence the group acts regularly on arcs. In that case, the vertex-stabiliser acts regularly on the neighbours, so it must be either cyclic of order $k$, or dihedral of order $k$ (in which case $k$ is even). These are all quite well studied objects, although not as much as the regular ones. In particular, they can be defined group-theoretically and, using this, can be enumerated up to a few thousand vertices and quite high genus, 100 say. (See math.auckland.ac.nz/~conder for example) $\endgroup$
    – verret
    Commented Apr 29, 2016 at 20:42
  • $\begingroup$ Isn't the vertex-edge flag graph somehow related to the line digraph? $\endgroup$
    – draks ...
    Commented May 16, 2017 at 15:23

1 Answer 1

Reset to default
4
$\begingroup$

It sounds like what you're asking for is close to the notion of "regular map":

  • Jozef Siran, "Regular Maps on a Given Surface: A Survey", Topics in Discrete Mathematics, 2006. (pdf)

A (connected) map $M$ is regular if its automorphism group acts transitively (and hence regularly) on the set of flags. On the other hand, the definition of "symmetry" you're using in the question is weaker than the standard definition of map automorphism, which in the case of maps embedded on compact oriented surfaces would restrict to orientation-preserving homeomorphisms (that also preserve the graph incidence relationships). This stronger definition rules out the cuboctahedron and icosidodecahedron, and indeed Siran asserts that the only regular maps on the sphere are the five platonic solids, the hosohedra ("$k$-dipoles") and the dihedra ("$k$-cycles") (plus the "semi-stars", if you allow graphs with dangling semi-edges).

Apparently a lot is also known about regular maps in the higher genus case! But since I'm not at all familiar with this, I'll just refer you to Siran's survey.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks, that's extremely helpful. It's a very readable paper. It only gets at a special case of my question. He does consider orientation-reversing symmetries, and even maps on nonorientable surfaces, but he only studies maps whose symmetries act transitively on vertex-edge-face flags, not more general ones where the symmetries act transitively on vertex-edge flags (or 'arcs'). Nonetheless, this special case is so mathematically natural that it's very fun to read about, and it gives a big pile of examples of what I want. $\endgroup$
    – John Baez
    Commented Apr 30, 2016 at 20:57
  • 1
    $\begingroup$ @JohnBaez Glad you found it useful! On v-e-f flags vs v-e flags, Siran's definition of regular map allows for nonorientable regular maps, but in the oriented case it seems natural to me to define regular maps as combinatorial maps $M = (D,v,e)$ such that $Aut(M)$ (respectively $Mon(M) = \langle v,e\rangle$) acts transitively (respectively, freely) on the set of darts $D$. Note that a dart is essentially the same thing as a v-e flag, except in the case of loops. I see that this definition of "oriented regular map" is considered by Roman Nedela here: savbb.sk/~nedela/CMbook.pdf. $\endgroup$
    – Noam Zeilberger
    Commented May 2, 2016 at 9:56
  • 1
    $\begingroup$ @JohnBaez On the other hand, this definition of "oriented regular map" would still rule out the cuboctahedron and the icosidodecahedron, since, for example, any automorphism of the cuboctahedron-as-combinatorial-map could not send a dart bordering a square to its left to a dart bordering a triangle to its left. $\endgroup$
    – Noam Zeilberger
    Commented May 2, 2016 at 9:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .