# 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 be a group acting faithfully on a set of size (equivalently, is a group embedded into the symmetric group on elements). A Jerrum-reduced generating set for is a generating set for such that the following graph associated with the generating set is acyclic:

- The vertices of the graph are elements of the set on which acts. Assume
- For each element of the generating set, there is one edge from the smallest element such that , to .

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.