Jerrum-reduced generating set
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
- 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.