Generating orbit representatives

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⁹ graphs on v=11 vertices). Thus we are looking for a method which allows to examine further cases, e.g. graphs of more than ten vertices, say. In order to cover such cases with some success, we have to accept redundancy and hence we shall ran into the isomorphism disease. Invariants, isomorphism tests and all that will have to be discussed. To begin with we need to check that we can generate orbit representatives uniformly at random.

 The Dixon/Wilf Algorithm If _GX denotes a finite action, then we can generate orbit representatives uniformly at random in the following way:

• Choose a conjugacy class C of G with probability

  p(C):=( | C | | X_g | )/( | G | | G\\X | ), where gÎC.

• Pick any gÎC and generate a fixed point of g, uniformly at random.

Then the probability that x is an element of the orbit wÎG\\X is 1/ | G\\X | , i.e. x is uniformly distributed over the orbits of G on X.

Proof: Let C₁,...,C_r denote the conjugacy classes of G, with representatives g_iÎC_i. Then, by the Cauchy-Frobenius lemma, we have

å_i=1^rp(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)=å_ip(C_i)p(xÎC_iÇw)

=å_ip(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Çw1= å_xÎwå_gÎXg1=å_xÎw | G_x | ,

which is equal to | G_y | | w | = | G | , for any yÎw, and we are done.

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 Y^X is easy, since we know the fixed points very well. Let us consider the G-classes, for example.

Corollary: For finite _GX and Y the following procedure yields elements fÎY^X that are distributed over the G-classes on Y^X uniformly at random:

• Choose a conjugacy class C of G with the probability

  p(C):=( | C | | Y | ^{c(bar (g'))})/(å_g | Y | ^{c( bar (g))}), g'ÎC.

• Pick any gÎC, evaluate its cycle decomposition and construct an fÎY^X that takes values yÎY on these cycles which are distributed uniformly at random over Y.

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),(2²),(2,1²) and (1⁴) of 4. Their orders are 6,8,3,6 and 1. The corresponding numbers of cyclic factors of the permutations induced on the set [4 choose 2] of pairs of vertices are 2,2,4,4 and 6, so that the numbers of fixed points on the set 2^{[4 choose 2]} of labeled graphs amount to 4,4,16,16 and 64. This yields for the probabilities p(C) the values

3/33,4/33,6/33,12/33,8/33.

These numbers may be multiplied by the common denominator 33 in order to get the natural numbers 3,4,6,12,8, which we accumulate obtaining

3,7,13, 25,33.

A generator that yields natural numbers between 1 and 33 uniformly at random is now used in order to choose 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 vertices

{a={1,2},b={1,3},c={1,4},d={2,3},e={2,4},f={3,4}}

the 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)(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 pairs a and f, 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 _GX is a finite action, w:X -> R a weight function, then G acts on the union of orbits with a prescribed weight rÎR, i.e. on the inverse image w^-1[{r}] of r, and we need only to replace in the Dixon/Wilf Algorithm the corresponding factors in the numerator and in the denominator obtaining

Corollary: If we choose the conjugacy class CÍG with the probability

p(C):=( | C | | w^-1[{r}]_g | )/( | G | | G\\w^-1[{r}] | ),

pick any element gÎC and generate a fixed point of weight r of g uniformly at random, then we obtain an element of X that is uniformly distributed over the orbits of weight r.

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. Here are a few of these numbers:

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 å_j=1^i-1p(C_j). The efficiency of this revised method heavily depends on the numbering of the conjugacy classes. The numbering should clearly be chosen in such a way that p(C_i)³p(C_i+1). Asymptotic considerations show (cf. Oberschelp, Dixon/Wilf) that in case of graph generation it is not bad to number the conjugacy classes of the symmetric group according to the lexicographic order of partitions.

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 the elements belonging to the X_V, where U is maximal in V. The remaining subset of X_U will be indicated as follows:

[^X] _U:=X_U\È_{U max.V}X_V.

The intersection of wÎX\\[~U] with [^X] _U is the orbit of an xÎw, where G_x=U, under the normalizer subgroup N_G(U), this is easy to check. As G_x=U we can even consider the action of the factor group N_G(U)/U on this intersection wÇ[^X] _U. This proves

Lemma: Each transversal of (N_G(U)/U)\\[^X] _U is a transversal of the orbits of type [~U] of G on X.

Moreover, if we want to apply probabilistic methods, we can use that the orbits of N_G(U)/U on [^X] _U are all of the same order | N_G(U)/U | . Hence we obtain

Theorem:  (Laue) By picking elements from the orbits of N_G(U)/U on [^X] _U uniformly at random, we obtain elements that are uniformly distributed over the orbits of type [~U] of G on X.

For example, if U:={1}, we have that [^X] _U=[^X] ₁ is equal to X minus the union of the fixed point sets X_V, taken over all the minimal subgroups V£G. If in particular G:=C_n, then the minimal subgroups V are just the cyclic subgroups C_p£C_n, where p is prime. the same holds for G:=S_n , but in this case there may be, of course, several such C_p. As N_G(1)=G, we can, according to Laue's theorem, easily generate representatives of the orbits of maximal length | bar (G) | , uniformly at random. In order to display a concrete example, we recall the enumeration of primitive polynomials of degree n over GF(q) (recall example). They correspond to the orbits of maximal length n of the Galois group C_n of GF(q)ⁿ over GF(q). The above reasoning shows that an orbit of G=N_G(1) on [^X] ₁ is also a transversal of these orbits of maximal length n of G on X. But [^X] ₁ is equal to GF(q)ⁿ minus the set of fixed points GF(q)_Cp, where p runs through the prime divisors of n. These subsets which have to be subtracted, can easily be spotted. For example, if n:=6,q:=2, C₆:=á(1...6)ñ, we obtain

GF(2)⁶_C2={000000,100100,010010,

001001,110110,101101, 011011,111111},

GF(2)⁶_C3={000000,101010,010101,111111}.

Subtracting the union of these sets from GF(2)⁶, we get [^X] ₁, consisting of the remaining 2⁶-10 binary sequences over GF(2). A transversal of the orbits of C₆ on [^X] ₁ is, for example. the set

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 conjugate g,g'ÎG, a finite action _GX and an orbit wÎG\\X, we have

| X_gÇw | = | X_g'Çw | .

Generating orbit representatives