schreierGraph -- Schreier graph of a finite group

Synopsis

Usage:

schreierGraph G
Inputs:
- G, an instance of the type FiniteGroupAction, a finite group action
Outputs:
- a hash table, representing the Schreier graph of the group

Description

This function is provided by the package InvariantRing.

For a finite group action, we form a HashTable whose keys are the generators provided by the user. The value corresponding to a generator g is a HashTable containing all pairs a => b such that a*g == b. This represents the Schreier graph of the group relative to the generating set provided by the user.

The following example defines the permutation action of a symmetric group on three elements using only two generators, a transposition and a 3-cycle.

i1 : R = QQ[x_1..x_3]

o1 = R

o1 : PolynomialRing

i2 : L = {matrix {{0,1,0},{1,0,0},{0,0,1}}, matrix {{0,0,1},{0,1,0},{1,0,0}} }

o2 = {| 0 1 0 |, | 0 0 1 |}
      | 1 0 0 |  | 0 1 0 |
      | 0 0 1 |  | 1 0 0 |

o2 : List

i3 : G = finiteAction(L, R)

o3 = R <- {| 0 1 0 |, | 0 0 1 |}
           | 1 0 0 |  | 0 1 0 |
           | 0 0 1 |  | 1 0 0 |

o3 : FiniteGroupAction

i4 : schreierGraph G

o4 = HashTable{0 => HashTable{| 0 0 1 | => | 0 0 1 |}}
                              | 0 1 0 |    | 1 0 0 |
                              | 1 0 0 |    | 0 1 0 |
                              | 0 0 1 | => | 0 0 1 |
                              | 1 0 0 |    | 0 1 0 |
                              | 0 1 0 |    | 1 0 0 |
                              | 0 1 0 | => | 1 0 0 |
                              | 0 0 1 |    | 0 0 1 |
                              | 1 0 0 |    | 0 1 0 |
                              | 0 1 0 | => | 1 0 0 |
                              | 1 0 0 |    | 0 1 0 |
                              | 0 0 1 |    | 0 0 1 |
                              | 1 0 0 | => | 0 1 0 |
                              | 0 0 1 |    | 0 0 1 |
                              | 0 1 0 |    | 1 0 0 |
                              | 1 0 0 | => | 0 1 0 |
                              | 0 1 0 |    | 1 0 0 |
                              | 0 0 1 |    | 0 0 1 |
               1 => HashTable{| 0 0 1 | => | 1 0 0 |}
                              | 0 1 0 |    | 0 1 0 |
                              | 1 0 0 |    | 0 0 1 |
                              | 0 0 1 | => | 1 0 0 |
                              | 1 0 0 |    | 0 0 1 |
                              | 0 1 0 |    | 0 1 0 |
                              | 0 1 0 | => | 0 1 0 |
                              | 0 0 1 |    | 1 0 0 |
                              | 1 0 0 |    | 0 0 1 |
                              | 0 1 0 | => | 0 1 0 |
                              | 1 0 0 |    | 0 0 1 |
                              | 0 0 1 |    | 1 0 0 |
                              | 1 0 0 | => | 0 0 1 |
                              | 0 0 1 |    | 1 0 0 |
                              | 0 1 0 |    | 0 1 0 |
                              | 1 0 0 | => | 0 0 1 |
                              | 0 1 0 |    | 0 1 0 |
                              | 0 0 1 |    | 1 0 0 |

o4 : HashTable

Ways to use schreierGraph :

schreierGraph(FiniteGroupAction)

For the programmer

The object schreierGraph is a method function.