Generating orbit representatives |

Proof: LetThe Dixon/Wilf AlgorithmIfdenotes a finite action, then we can generate orbit representatives uniformly at random in the following way:_{G}XThen the probability that

- Choose a conjugacy class
CofGwith probabilityp(C):=(| C | | X_{g}|)/(| G | | G\\X |), where gÎC.- Pick any
gÎCand generate a fixed point ofg, uniformly at random.xis an element of the orbitwÎG\\Xis1/ | G\\X |, i.e.xis uniformly distributed over the orbits ofGonX.

so thatå_{i=1}^{r}p(C_{i})=(å_{i}| C_{i}| | X_{gi}|)/(å_{g}| X_{g}|)=1,

p(xÎw)=å_{i}p(C_{i})p(xÎC_{i}Çw)

=å_{i}p(C_{i})(| X_{gi}Çw |)/(| X_{gi}|)=å_{i}(| C_{i}| | X_{gi}|)/(| G | | G\\X |)(| X_{gi}Çw |)/(| X_{gi}|)

where the last identity follows from exercise. Now=(1)/(| G | | G\\X |)å_{i}| C_{i}| | X_{gi}Çw | =(1)/(å_{g}| X_{g}|)å_{g}| X_{g}Çw | ,

which is equal toå_{g}| X_{g}Çw | =å_{gÎG}å_{xÎXgÇw}1= å_{xÎw}å_{gÎXg}1=å_{xÎw}| G_{x}| ,

The application of this method to the generation of representatives of
*G*-classes, *H*-classes, *H´G*-classes and *H wr _{X} G *-classes on

Consider our standard example for this situation:Corollary:For finiteand_{G}XYthe following procedure yields elementsfÎYthat are distributed over the^{X}G-classes onYuniformly at random:^{X}

- Choose a conjugacy class
CofGwith the probabilityp(C):=(| C | | Y |^{c(bar (g'))})/(å_{g}| Y |^{c( bar (g))}), g'ÎC.- Pick any
gÎC, evaluate its cycle decomposition and construct anfÎYthat takes values^{X}yÎYon these cycles which are distributed uniformly at random overY.

Example:We would like to generate graphs on 4 vertices uniformly at random. The conjugacy classes are parametrized by the proper partitions(4),(3,1),(2and^{2}),(2,1^{2})(1of 4. Their orders are 6,8,3,6 and 1. The corresponding numbers of cyclic factors of the permutations induced on the set^{4})[of pairs of vertices are 2,2,4,4 and 6, so that the numbers of fixed points on the set4choose 2]2of labeled graphs amount to 4,4,16,16 and 64. This yields for the probabilities^{[4 choose 2]}p(C)the valuesThese numbers may be multiplied by the common denominator 33 in order to get the natural numbers 3,4,6,12,8, which we accumulate obtaining3/33,4/33,6/33,12/33,8/33.A generator that yields natural numbers between 1 and 33 uniformly at random is now used in order to choose3,7,13, 25,33.C. As soon as it generates one of the numbers 1,2 or 3 this means that the first one of the conjugacy classes is chosen. If it generates 4,5,6 or 7, the second class is chosen, and so on. Assume that it generates 12, then the third conjugacy class is picked, an element of which is the permutation(12)(34). It induces on the set of pairs of verticesthe permutation A random generator of zeros and ones is now used in order to associate values 0 or 1 with the cyclic factors of{a={1,2},b={1,3},c={1,4},d={2,3},e={2,4},f={3,4}}(a)(be)(cd)(f). If it generates the sequence 1,0,0,1,say, we obtain the labelled graph that has edges joining the elements of the pairsaandf, while all the other pairs of vertices remain disjoint. Its orbit is represented by the graph shown in figure.The generated graph

This method can easily be refined in order to generate graphs with prescribed
number of edges or, more generally, representatives of orbits with a given
weight, uniformly at random. If * _{G}X* is a finite action,

In the case when the acting group is a symmetric group, the choice of a conjugacy class amounts to the choice of a proper partition. We therefore should not forget that the number of proper partitions ofCorollary:If we choose the conjugacy classCÍGwith the probabilitypick any elementp(C):=(| C | | w^{-1}[{r}]_{g}|)/(| G | | G\\w^{-1}[{r}] |),gÎCand generate a fixed point of weightrofguniformly at random, then we obtain an element ofXthat is uniformly distributed over the orbits of weightr.

This shows that it is worthwile to try to avoid that this amount of probabilities is stored throughout the whole generating process. For practical purposes one can start the generation and evaluate probabilities only if required. This means that we need to evaluate

n no. of proper partitions 10 42 20 627 40 37338 60 »10^6 100 »2·10^8

In order to generate representatives of the
orbits of *G* on *X* with prescribed
type *[~U] *, we can do the following. As each such orbit
*wÎG\\X* does contain elements *x* which have *U* as stabilizer,
we can cut off from *X _{U}* each element that has a bigger stabilizer. It
clearly suffices to remove from

The intersection of[^X]_{U}:=X_{U}\È_{U max.V}X_{V}.

Moreover, if we want to apply probabilistic methods, we can use that the orbits ofLemma:Each transversal of(Nis a transversal of the orbits of type_{G}(U)/U)\\[^X]_{U}[~U]ofGonX.

For example, ifTheorem:(Laue)By picking elements from the orbits ofNon_{G}(U)/U[^X]uniformly at random, we obtain elements that are uniformly distributed over the orbits of type_{U}[~U]ofGonX.

GF(2)^{6}_{C2}={000000,100100,010010,

001001,110110,101101, 011011,111111},

Subtracting the union of these sets fromGF(2)^{6}_{C3}={000000,101010,010101,111111}.

Assuming a normal basis given, we can translate these sequences into the 9 corresponding polynomials that are listed in many books.100000,110000,101000,10010,111000,110100,110010,111100,111110.

**Exercises**

E:Prove that, for conjugateg,g'ÎG, a finite actionand an orbit_{G}XwÎG\\X, we have| X_{g}Çw | = | X_{g'}Çw | .

harald.fripertinger@kfunigraz.ac.at,

last changed: August 28, 2001

Generating orbit representatives |