Graph symmetry

October 14, 2010

tags: Cayley graphs, graph, primitive permutation group, quasiprimitive

John claims that he and Gordon are confused by the various adjectives used by us graph symmetry people and how they relate to each other so I have decided to write some posts outlining the main ones and their importance. There is a nice diagram on wikipedia illustrating the relationship between the main ones and I will use that as the basis of my discussion.

Throughout I will use ${\Gamma}$ to denote a graph and ${G}$ to denote a group (unfortunately some authors use the reverse.) All graphs will be simple (that is, undirected, no multiple edges, and no loops) and finite. The full automorphism group of a graph, that is the group of all permutations of the set of vertices that take edges to edges, will be denoted by ${\mathrm{Aut}(\Gamma)}$ . I will use ${V\Gamma}$ to denote the set of vertices, ${E\Gamma}$ to denote the set of edges and ${A\Gamma}$ to denote the set of arcs, that is the set of ordered pairs of adjacent vertices.

The first adjective is regular. A graph is called regular if each vertex has the same number of neighbours. This number is referred to as the valency of the graph.

A graph is called vertex-transitive if ${\mathrm{Aut}(\Gamma)}$ acts transitively on the set of vertices, that is, for all ${v, u\in V\Gamma}$ there exists an automorphism ${g}$ such that ${u^g=v}$ . Sometimes we wish to restrict our attention to a subgroup ${G}$ of ${\mathrm{Aut}(\Gamma)}$ and say that ${\Gamma}$ is ${G}$ -vertex-transitive if ${G}$ acts transitively on ${V\Gamma}$ .

One consequence of a graph being vertex-transitive is that it is regular: if an automorphism ${g}$ maps ${u}$ to ${v}$ then it also maps the neighours of ${u}$ to the nieghbours of ${v}$ . However, not all regular graphs are vertex-transitive. In fact, it is even possible for a regular graph to have a trivial automorphism group, for example, the Frucht graph.

Another consequence of being vertex-transitive, is that if the graph is disconnected, then the connected components are all isomorphic: automorphisms must map connected components to connected components and vertex-transitivity implies that you can map any connected component to any other connected component. It follows that if you wish to study vertex-transitive graphs you only need to study the connected ones.

In one sense vertex-transitive graphs are easy to construct. Given any permutation group ${G\leqslant \mathrm{Sym}(\Omega)}$ , we can construct a ${G}$ -vertex-transitive graph ${\Gamma}$ with vertex set ${\Omega}$ as follows: Pick a few pairs ${\{u_1,v_1\}, \ldots,\{u_t,v_t\}}$ of elements of ${\Omega}$ and let the edge set of ${\Gamma}$ be the union of the sets ${\{u_i,v_i\}^G}$ , that is we choose some pairs to be edges, and then spin them under ${G}$ to find the remaining edges. It follows that ${G\leqslant\mathrm{Aut}(\Gamma)}$ . However, not every transitive permutation group ${G}$ is the full automorphism group of a graph. For example, the cyclic group of order 3 is not the full automorphism group of a graph with 3 vertices.

One restriction we can then make is to place further conditions on the action on vertices. For example we could look at vertex-primitive graphs, that is those for which the full automorphism group acts primitively on the set of vertices. We could also look at the larger class of vertex-quasiprimitive graphs where the full automorphism group acts quasiprimitively on the set of vertices. We can also refer to ${G}$ -vertex-primitive and ${G}$ -vertex-quasiprimitive for some ${G\leqslant\mathrm{Aut}(\Gamma)}$ . We need to be a bit careful here though. An overgroup of a primitive group is still primitive, so if ${\Gamma}$ is ${G}$ -vertex-primitive for some ${G}$ then ${\mathrm{Aut}(\Gamma)}$ is primitive on vertices. However, if ${\Gamma}$ is ${G}$ -vertex-quasiprimitive then ${\mathrm{Aut}(\Gamma)}$ may or may not be quasiprimitive on vertices.

One way to study vertex-primitive and vertex-quasiprimitive graphs is via the O’Nan-Scott Theorem for primitive or quasiprimitive groups. Vertex-primitive and vertex-quasiprimitive graphs usually arise as “basic graphs” when we are studying some family of graphs via quotients. Vertex-primitive graphs have no meaningful quotients with respect to partitions of the vertex set preserved by the automorphism group, while vertex-quasiprimitive graphs have no meaningful normal quotients, that is, quotients with respect to the set of orbits of some normal subgroup of ${\mathrm{Aut}(\Gamma)}$ .

I should note that it is not that interesting to study graphs for which the full automorphism group is 2-transitive on vertices. The only such graph are the complete graph, where any two vertices are adjacent, or the empty graph, where there are no edges.

An important class of graphs are bipartite graphs. If ${\Gamma}$ is a bipartite graph, then we let ${\mathrm{Aut}(\Gamma)^+}$ be the group of all automorphisms that fix each bipartite half setwise. If ${\Gamma}$ is vertex-transitive then this is an index 2 subgroup of ${\mathrm{Aut}(\Gamma)}$ while if ${\Gamma}$ does not have an automorphism interchanging the two bipartite halves then ${\mathrm{Aut}(\Gamma)^+=\mathrm{Aut}(\Gamma)}$ . Given ${G\leqslant \mathrm{Aut}(\Gamma)}$ we can also define ${G^+}$ similarly.

A bipartite graph cannot be vertex-primitive as the bipartition forms a system of imprimitivity. Moreover, it cannot be vertex-quasiprimitive as ${\mathrm{Aut}(\Gamma)^+}$ is an intransitive normal subgroup. For these reasons it is best to look at the notions of vertex-biprimitive and vertex-biquasiprimitive and as before these will arise as the “basic” bipartite graphs when doing a quotient analysis.

Care needs to be taken here though as there are varying definitions in the literature. I prefer to say that a graph is ${G}$ -vertex-biquasiprimitive if ${G}$ is transitive on vertices, all normal subgroups of ${G}$ are either transitive or have two orbits on vertices, and there is a normal subgroup with two orbits on vertices. In some sense they are as close to being quasiprimitive as possible. The corresponding definition for ${G}$ -vertex-biprimitive is then that ${G}$ is imprimitive on vertices and each system of imprimitivity has precisely two blocks. However, it is common in the literature to refer to a bipartite graph as being ${G}$ -vertex-biprimitive if ${G^+}$ acts primitively on each bipartite half (such a definition usually also allows ${G=G^+}$ ). The two definitions are not equivalent but I prefer the first since then a ${G}$ -vertex-biquasiprimitive graph is ${G}$ -vertex-biprimitive, while this would not be true it we chose the second definition.

I should finish this post by briefly discussing Cayley graphs. Given a group ${G}$ and a subset ${S}$ such that ${S=S^{-1}}$ and ${1_G\notin S}$ we can define the Cayley graph ${Cay(G,S)}$ whose vertices are the elements of ${G}$ and two elements ${g,h}$ are adjacent if and only if ${gh^{-1}\in S}$ . The group ${G}$ acts by right multiplication as a group of automorphisms of ${Cay(G,S)}$ so Cayley graphs are vertex-transitive.

Not every vertex-transitive graph is a Cayley graph, for example the Petersen graph is not a Cayley graph. In fact, a graph is a Cayley graph if and only if ${\mathrm{Aut}(\Gamma)}$ contains a regular subgroup. It has been conjectured by Brendan McKay and Cheryl Praeger that as ${n}$ goes to infinity the proportion of vertex-transitive graphs with ${n}$ vertices that are Cayley graphs goes to 1.

John has asked for Venn diagrams so here is one for this post.

In the next post I will look at symmetry conditions related to edges and arcs.

Like this:

Be the first to like this post.

One Comment leave one →

John Bamberg permalink*

October 15, 2010 10:06 am

I am eager to see the next Venn diagram. How do local and global symmetry assumptions on edges and arcs limit the possible examples? Perhaps you could colour your Venn diagram in:

- Red: generally understood to be a wild class of examples, impossible to characterise.
- Green: Completely characterised. We understand all of the examples from a known list of constructions.
- Yellow: We kind of understand the class but there remain interesting open questions.

Reply

	Peter Cameron on Science without stats
	Michael Giudici on Symmetries of Discrete Ob…
	Gordon Royle on Symmetries of Discrete Ob…
	Gordon Royle on Science without stats
	John Bamberg on Science without stats

just another maths blog

Graph symmetry

Like this:

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Tags

Categories

Blogroll

Feeds

Visitors

Follow “SymOmega”