# 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 \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.