Group Action Orbital

• Let be a transitive permutation group acting on . Of interest to us is acting on the pairs . The orbits of acting on are sometimes called orbitals ¹

• The diagonal orbital is defined as the set

• If , then the transpose is defined as

  • is -invariant if and only if is.

• If is an orbit of ,, then there are only two cases

  • , the symmetric case
  • , the disjoint case.

• (Godsil 2.4.1) Let be a group acting transitively on , where . Then there is a one-to-one correspondence

• If is symmetric, then the corresponding orbit of is said to be self-paired. ²

• (Godsil 2.4.2) Let be a transitive permutation group on and . Suppose . Then is symmetric if and only if there is a permutation such that

• A permutation group on is generously transitive if, for any distinct there is a permutation that swaps them.

  • All are symmetric if and only if is generously transitive.

• (Godsil e2.11) Let be a transitive permutation group on . has a symmetric nondiagonal orbit on if and only if is even.

  • Proof: If has a symmetric nondiagonal orbit on where then by its symmetry, . We can, therefore, partition into two groups. Hence is even and by the Orbit-Stabilizer theorem, is even.

    Conversely, if is even, then by Cauchy’s theorem, contains which is of order . By transitivity, it must swap at least two elements . The orbit contains both and . Clearly and also is closed under swapping, so it is symmetric nondiagonal.

Links §

• Algebraic Graph Theory by Godsil and Royle

Footnotes §

1. Note the similarities with Matrices ↩

2. One nice example of this. If we consider a group acting on a graph with vertex set and arc-set then if is self-paired, the graph is undirected. Otherwise it is oriented. ↩