Jerrum-reduced generating set

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\neq 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

• Permutation-invariantly Jerrum-reduced generating set: This is a generating set that is Jerrum-reduced for any choice of ordering of the underlying set it is acting on.