Generating orbit representatives |

The evaluation of an orbit transversal
is of limited use since these sets are
usually very (for example there are approximately *10 ^{9}* graphs on

The 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.

Proof: Let *C _{1},...,C_{r}* denote the conjugacy classes of

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

so that *p(-)* defines in fact a probability distribution. If *wÎG\\X*, then

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}|)

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

where the last identity follows from exercise. Now

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

which is equal to * | G _{y} | | w | = | G | *, for any

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

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.

Consider our standard example for this situation:

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,

Corollary: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.

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 of *nÎ N*
is rapidly increasing with

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

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 *p(C _{i})* only if the
generated random number exceeds

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

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

The intersection of *wÎX\\[~U] * with *[^X] _{U}* is the
orbit of an

Lemma:Each transversal of(Nis a transversal of the orbits of type_{G}(U)/U)\\[^X]_{U}[~U]ofGonX.

Moreover, if we want to apply probabilistic methods, we can use that the orbits
of *N _{G}(U)/U* on

Theorem:(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.

For example, if *U:={1}*, we have that *[^X] _{U}=[^X] _{1}* is equal to

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

001001,110110,101101, 011011,111111},

GF(2)^{6}_{C3}={000000,101010,010101,111111}.

Subtracting the union of these sets from *GF(2) ^{6}*, we get

100000,110000,101000,10010,111000,110100,110010,111100,111110.

Assuming a normal basis given, we can translate these sequences into the 9 corresponding polynomials that are listed in many books.

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 "at" uni-graz.at | http://www-ang.kfunigraz.ac.at/~fripert/ |

UNI-Graz | Institut für Mathematik |

UNI-Bayreuth | Lehrstuhl II für Mathematik |

Generating orbit representatives |