[MathJax on]

4 Constraints

4.1 The concept of constraints in BacktrackKit

Fundamentally, the partition backtrack algorithm (and its generalisations) performs a search for permutations that satisfy a collection of constraints.

A constraint is a true/false mathematical property of permutations, such that if the set of permutations satisfying the property is nonempty, then that set must be a (possibly infinite) permutation group, or a coset thereof. Furthermore, it must be ‘easy’ to test whether any given permutation satisfies the property.

For example:

• “is a member of the group G = \langle X \rangle”,

• “transports the set A to the set B”,

• “commutes with the permutation x”,

• “conjugates the group G = \langle X \rangle to the group H = \langle Y \rangle”,

• “is an automorphism of the graph \Gamma”, and

• “is even”

are all examples of constraints. On the other hand:

• “is a member of the socle of the group G”, and

• “is a member of a largest maximal subgroup of the group G”

do not qualify, unless generating sets for the socle and the largest maximal subgroups of G are already known, and there is a unique such maximal subgroup (in which case these properties become instances of the constraint “is a member of the group defined by the generating set...”).

The term ‘constraint’ comes from the computer science field of constraint satisfaction problems, constraint programming, and constraint solvers, with which backtrack search algorithms are very closely linked.

BacktrackKit provides a number of built-in constraints. Constraints, and the functions to create them, are contained in the Constraint (4.2-1) record. The members of this record are documented individually in Section 4.3.

To use BacktrackKit, it is necessary to (at least implicitly) specify constraints that, in conjunction, define the permutation(s) that you wish to find. This is documented in Chapter 2. A constraint will typically be converted into one or more refiners by that the time that a search takes place. Refiners are introduced in Chapter 5. We do not yet explicitly document the conversion of BacktrackKit constraints into refiners; the conversion may change in future versions of BacktrackKit.

4.2 The Constraints record

4.2-1 Constraint

Constraint is a record that contains functions for producing all of the constraints that BacktrackKit provides.

The members of Constraint are documented individually in Section 4.3.

The members whose names differ only by their “-ise” and “-ize” endings are synonyms, included to accommodate different spellings in English.

gap> LoadPackage("BacktrackKit", false);;
gap> Set(RecNames(Constraint));
[ "Centralise", "Centralize", "Conjugate", "InCoset", "InGroup", 
  "InLeftCoset", "InRightCoset", "IsEven", "IsOdd", "IsTrivial", 
  "LargestMovedPoint", "MovedPoints", "None", "Normalise", "Normalize", 
  "Nothing", "Stabilise", "Stabilize", "Transport" ]

4.3 Constraints via the Constraint record

In this section, we individually document the functions of the Constraint (4.2-1) record, which can be used to create the built-in constraints provided by BacktrackKit.

Many of these constraints come in pairs, with a “group” version, and a corresponding “coset” version. These relationships are given in the following table.

4.3-1 Constraint.InGroup

Returns: A constraint

This constraint is satisfied by precisely those permutations in the permutation group G.

gap> con1 := Constraint.InGroup(DihedralGroup(IsPermGroup, 8));
<constraint: in group: Group( [ (1,2,3,4), (2,4) ] )>
gap> con2 := Constraint.InGroup(AlternatingGroup(4));
<constraint: in group: AlternatingGroup( [ 1 .. 4 ] )>

4.3-2 Constraint.InCoset

Returns: A constraint

This constraint is satisfied by precisely those permutations in the GAP right coset object U.

See also Constraint.InLeftCoset (4.3-4) and Constraint.InRightCoset (4.3-3), which allow a coset to be specifed by a subgroup and a representative element.

gap> U := PSL(2,5) * (3,4,6);
RightCoset(Group([ (3,5)(4,6), (1,2,5)(3,4,6) ]),(3,4,6))
gap> Constraint.InCoset(U);
<constraint: in coset: Group( [ (3,5)(4,6), (1,2,5)(3,4,6) ] ) * (3,4,6)

4.3-3 Constraint.InRightCoset

Returns: A constraint

This constraint is satisfied by precisely those permutations in the right coset of the group G determined by the permutation x.

See also Constraint.InLeftCoset (4.3-4) for the left-hand version, and Constraint.InCoset (4.3-2) for a GAP right coset object.

gap> Constraint.InRightCoset(PSL(2,5), (3,4,6));
<constraint: in coset: Group( [ (3,5)(4,6), (1,2,5)(3,4,6) ] ) * (3,4,6)

4.3-4 Constraint.InLeftCoset

Returns: A constraint

This constraint is satisfied by precisely those permutations in the left coset of the group G determined by the permutation x.

See also Constraint.InRightCoset (4.3-3) for the right-hand version, and Constraint.InCoset (4.3-2) for a GAP right coset object.

gap> Constraint.InLeftCoset(PSL(2,5), (3,4,6));
<constraint: in coset: Group( [ (3,6)(4,5), (1,2,5)(3,4,6) ] ) * (3,4,6)

4.3-5 Constraint.Transport

Returns: A constraint

This constraint is satisfied by precisely those permutations that map object1 to object2 under the given group action, i.e. all permutations g such that action(object1,g)=object2. Note that the set of such permutations may be infinite.

The combinations of objects and actions that are supported by Constraint.Transport are given in the table below.

gap> setofsets1 := [[1, 3, 6], [2, 3, 6]];;
gap> setofsets2 := [[1, 2, 5], [1, 5, 7]];;
gap> con := Constraint.Transport(setofsets1, setofsets2, OnSetsSets);
<constraint: transporter of [ [ 1, 3, 6 ], [ 2, 3, 6 ] ] to [ [ 1, 2, 5 ], [ 1\
, 5, 7 ] ] under OnSetsSets>

4.3-6 Constraint.Stabilise

Returns: A constraint

This constraint is satisfied by precisely those permutations that fix object under the given group action, i.e. all permutations g such that action(object,g)=object. Note that the set of such permutations may be infinite.

The combinations of objects and actions that are supported by Constraint.Stabilise are given in the table below.

gap> con1 := Constraint.Stabilise(CycleDigraph(6), OnDigraphs);
<constraint: stabiliser of CycleDigraph(6) under OnDigraphs>
gap> con2 := Constraint.Stabilise([2,4,6], OnSets);
<constraint: stabiliser of [ 2, 4, 6 ] under OnSets>

4.3-7 Constraint.Normalise

Returns: A constraint

This constraint is satisfied by precisely those permutations that normalise the permutation group G, i.e. that preserve G under conjugation.

Note that the set of such permutations is infinite.

gap> Constraint.Normalise(PSL(2,5));
<constraint: normalise Group( [ (3,5)(4,6), (1,2,5)(3,4,6) ] )>

4.3-8 Constraint.Centralise

Returns: A constraint

This constraint is satisfied by precisely those permutations that commute with G, if G is a permutation, or that commute with every element of G, if G is a permutation group.

Note that the set of such permutations is infinite.

gap> D12 := DihedralGroup(IsPermGroup, 12);;
gap> Constraint.Centralise(D12);
<constraint: centralise group Group( [ (1,2,3,4,5,6), (2,6)(3,5) ] )>
gap> x := (1,6)(2,5)(3,4);;
gap> Constraint.Centralise(x);
<constraint: centralise perm (1,6)(2,5)(3,4)>

4.3-9 Constraint.Conjugate

Returns: A constraint

This constraint is satisfied by precisely those permutations that conjugate x to y, where x and y are either both permutations, or both permutation groups.

Note that the set of such permutations may be infinite.

This constraint is equivalent to Constraint.Transport(x,y,OnPoints).

gap> Constraint.Conjugate((3,4)(2,5,1), (1,2,3)(4,5));
<constraint: conjugate perm (1,2,5)(3,4) to (1,2,3)(4,5)>

4.3-10 Constraint.MovedPoints

Returns: A constraint

This constraint is a shorthand for Constraint.InGroup(SymmetricGroup(pointlist)). See Constraint.InGroup (4.3-1).

gap> con1 := Constraint.MovedPoints([1..5]);
<constraint: moved points: [ 1 .. 5 ]>
gap> con2 := Constraint.MovedPoints([2,6,4,5]);
<constraint: moved points: [ 2, 6, 4, 5 ]>

4.3-11 Constraint.LargestMovedPoint

Returns: A constraint

This constraint is a shorthand for Constraint.InGroup(SymmetricGroup(point)), where point is a nonnegative integer. See Constraint.InGroup (4.3-1).

gap> con := Constraint.LargestMovedPoint(5);
<constraint: largest moved point: 5>

4.3-12 Constraint.IsEven

This constraint is satisfied by the even permutations, i.e. those permutations with sign 1. In other words, this constraint restricts a search to some alternating group.

Note that the set of such permutations is infinite.

gap> Constraint.IsEven;
<constraint: is even permutation>
gap> Representative(Constraint.IsEven);
()

4.3-13 Constraint.IsOdd

This constraint is satisfied by the odd permutations, i.e. those permutations with sign -1. In other words, this constraint restricts a search to the unique coset of some alternating group.

Note that the set of such permutations is infinite.

gap> Constraint.IsOdd;
<constraint: is odd permutation>
gap> Representative(Constraint.IsOdd);
(1,2)

4.3-14 Constraint.IsTrivial

This constraint is satisfied by the identity permutation and no others.

This constraint will typically not be required by the user.

gap> Constraint.IsTrivial;
<trivial constraint: is identity permutation>
gap> Representative(Constraint.IsTrivial);
()

4.3-15 Constraint.None

This constraint is satisfied by no permutations.

This constraint will typically not be required by the user.

gap> Constraint.None;
<empty constraint: satisfied by no permutations>
gap> Representative(Constraint.None);
fail

generated by GAPDoc2HTML