Jerrum-reduced generating set

From Groupprops
Jump to: navigation, search

This article defines a property that can be evaluated for a generating set of a permutation group: a group equipped with an embedding in a symmetric group on an ordered set

Definition

Let G be a group acting faithfully on a set S of size n (equivalently, G is a group embedded into the symmetric group on n elements). A Jerrum-reduced generating set for G is a generating set for G such that the following graph associated with the generating set is acyclic:

  • The vertices of the graph are elements of the set S on which G acts. Assume S = \{ 1 ,2, 3, \ldots, n \}
  • For each element g of the generating set, there is one edge from the smallest element s \in S such that g.s \ne s, to g.s.

Note that the notion of Jerrum-reduced depends on a total ordering of the set on which the group acts. In particular, it is possible for a generating set to be Jerrum-reduced for one choice of ordering but to not be Jerrum-reduced for some other choice of ordering.

Jerrum's filter is an online algorithm which gives a process of starting from any generating set and Jerrum-reducing it. Moreover, for a generating set that is already Jerrum-reduced, the algorithm proceeds virtually instantaneously.

Relation with other properties

Stronger properties