ALCOMFT-TR-01-4

Leslie Ann Goldberg
Computation in permutation groups: counting and randomly sampling orbits
Warwick. Work package 4. January 2001.

Abstract: Let Omega be a finite set and let G be a permutation group acting on Omega. The permutation group G partitions Omega into orbits. This survey focuses on three related computational problems, each of which is defined with respect to a particular input set I. The problems, given an input (Omega,G)\in I, are (1) count the orbits (exactly), (2) approximately count the orbits, and (3) choose an orbit uniformly at random. The goal is to quantify the computational difficulty of the problems. In particular, we would like to know for which input sets I the problems are tractable.

Postscript file: ALCOMFT-TR-01-4.ps.gz (156 kb).