part := [ Set([2,3,6]), Set([1]), Set([4,5]) ];[ [ 2, 3, 6 ], [ 1 ], [ 4, 5 ] ]Intro to Ordered Partitions
This section introduces ordered partitions, which are used in both graph isomorphism and partition backtracking. We will give a definition and provide a simple (and inefficient!) implementation of ordered partitions in GAP.
This post is (probably) only of interest if you want to learn about graph isomorphism or partition backtracking!
An ordered partition of a set \(\Omega\) is a partition of \(\Omega\) where the cells of the partition are ordered. Let’s give an example!
Given the set \(\{1\ldots 6\}\), one ordered partition is \([\{2,3,6\}, \{1\}, \{4,5\}]\). Here the first cell of the partition is the set \(\{2,3,6\}\), the second is \(\{1\}\) and the last is \(\{4,5\}\). No value occurs in more than one cell, and the unions of the cells is \(\{1\ldots 6\}\).
Given an ordered partition, we can ask for the cell of some \(o \in \Omega\), which will give us the index of the cell which contains \(o\).
Explicit representation
How can we represent an ordered partition in GAP? There are a couple of different options, with different tradeoffs. The easiest option is as a list of sets. We will call this the explicit representation:
We can sanity check we have all our values by using Union to merge our list of sets:
Union(part);
# [1 .. 6 ][ 1 .. 6 ]Indicator Representation
There is one bad feature of this representation – it is expensive to find which cell a particular \(o
\in \Omega\) is contained in, as we have to search through the cells in turn. Therefore let us consider a second representation, known as the simple indicator representation. This maps each value to the the cell it is contained in. For example, part from the previous example is represented by the list l := [2,1,1,3,3,1]. The simple indicator and explicit representations are linked by the condition \(l[i] = j \leftrightarrow j \in part[i]\) .
Complex Indicator Representation
Our final representation is known as the complex indicator representation. This is just like the simple indicator representation, except we allow the array to contain any values, not just the integers in a range [1..k]. For example, lx := [2, -6, -6, "Q", "Q", -6]. Two values \(i\) and \(j\) are in the same cell of the partition if and only if \(lx[i] = lx[j]\).
But wait, we want ordered partitions! What ordering is there on 2, -6 and "Q"? When we use the complex indicator representation we assume there is a total ordering on the labels we use for cells. We will never need to care what this total ordering is, but we need it to exist. GAP provides a complete ordering on (almost) all objects, where for example all integers are less than "Q", and in fact all strings. By design, all simple indicator representations are also complex indicator representation.
Here are a couple of GAP functions, which provide mappings between the explicit and complex indicator representations. Firstly, we will map explicit to simple indicator. We will test it with our running example.
ExplicitToIndicator := function(cells)
local cellpos, i, j;
cellpos := [];
# Iterate over all the cells
for i in [1..Length(cells)] do
# Iterate over the members of each cell
for j in cells[i] do
cellpos[j] := i;
od;
od;
return cellpos;
end;;
ExplicitToIndicator([ [2,3,6], [1], [4,5] ]);[ 2, 1, 1, 3, 3, 1 ]Now, let’s go back the other way, from explicit indicator back to explicit. This function first gathers all the labels we used, then uses the Position function to find the location of each value in our ordering partition.
IndicatorToExplicit := function(cellpos)
local cells, labels, i;
# Find all unique cell labels
labels := Set(cellpos);
# make an empty list of cells
cells := List([1..Length(labels)], x -> []);
# Fill the cells
for i in [1..Length(cellpos)] do
AddSet(cells[Position(labels, cellpos[i])], i);
od;
return cells;
end;;
IndicatorToExplicit( [ 2, 1, 1, 3, 3, 1 ] );
IndicatorToExplicit( [2, -6, -6, "Q", "Q", -6] );[ [ 2, 3, 6 ], [ 1 ], [ 4, 5 ] ][ [ 2, 3, 6 ], [ 1 ], [ 4, 5 ] ]Refining Partitions
Why have these two different representations? In particular, the indicator representation feels much less mathematically nice, particularly the complex indicator. The reason we use this representation is it makes it easy to express one of the most important operations we will perform on ordered partitions, refinement.
Given two ordered partitions \(P\) and \(Q\), which both partition the same set \(\{1\ldots n\}\), \(Q\) is a refinement of \(P\) if every cell of \(Q\) is contained in a cell of \(P\). Alternatively, \(Q\) can be created by splitting cells of \(P\).
Important Aside: There is another definition of refinement which is stricter and imposes an order on the cells of \(Q\) – this requires, if \(P\) has \(j\) cells, that \(\forall i \in \{1\dots j\}. Q[i] \subseteq P[i]\). We won’t consider that here, but it may come up in future sections. We will discuss it when it does.
Let’s consider a couple of ways of taking a partition, and generating a refinement of it. These will both be used over and over again in both partition backtrack, and when finding graph automorphism.
Fixing a single point
Consider a partition in explicit format – let’s consider our long-running example part := [ [2,3,6], [1], [4,5] ];. We want to take this and generate a new partition, where a single value has been extracted an placed in a cell by itself. For example, if we fixed 3, we might get [ [2,6], [1], [4,5], [3] ]. Alternatively, we might get [ [1], [3], [2,6], [4,5] ], because we don’t care about the order of the cells, just their contents.
The easiest way to fix a single point is to switch to indicator representation, and change the value. Here is a function which accepts, and returns, an explicit input. All we need to is give our point a label which no other cell has.
FixPoint := function(cells, point)
local indic;
indic := ExplicitToIndicator(cells);
indic[point] := "fix";
return IndicatorToExplicit(indic);
end;;
FixPoint( [ [2,3,6], [1], [4,5] ], 3);[ [ 2, 6 ], [ 1 ], [ 4, 5 ], [ 3 ] ]The meet of two partitions
Given two ordered partitions P and Q, we can define their meet as a new partition R, where two values are in the same cell of R if and only if they are in the same cells of both P and Q. Implementing this is easy with the complex indicator representation, as we can just make a label for each value made from the pair of it’s label in P and Q. We calculate the meet partitions frequently during partition backtracking.
PartitionsMeet := function(P, Q)
local indicP, indicQ, indicJoin;
indicP := ExplicitToIndicator(P);
indicQ := ExplicitToIndicator(Q);
indicJoin := List([1..Length(indicP)], i -> [indicP[i], indicQ[i]]);
return IndicatorToExplicit(indicJoin);
end;;
PartitionsMeet([ [1,2,3], [4,5] ], [ [1,2], [3,4,5] ]);;Applying permutations to partitions
Given an ordered partition Q and a permutation p, we define the action of p on Q as mapping each point in each cell of Q by p. For representations in the Explicit format, GAP already has a function to do this: OnTuplesSets:
OnTuplesSets([ [2,3,6], [1], [4,5] ], (1,2,3,4,5,6));[ [ 1, 3, 4 ], [ 2 ], [ 5, 6 ] ]In outrsearches, we will often want to look at all the permutations which map an ordered partition to itself, or one ordered partition to another. We will now give some important basic results in this area. We will not prove these here, but the results are not complicated.
- Given an ordered partition \(P\), the set of permutations \(p\) such that \(P^p = P\) is generated by the product of the symmetric group of each cell of \(P\).
GAP already uses this result internally to quickly calculate the stabilizer of an list of sets.
Stabilizer(SymmetricGroup(5), [ [1,3], [2,4,5] ], OnTuplesSets);Group([ (1,3), (2,4,5), (2,4) ])Definition: Two ordered partitions P and Q are agreeable if the number of cells in P is equal to the number of cells in Q, and for all i, the size of P[i] is equal to the size of Q[i]. This is, I think, easier to read as a function!
Agreeable := function(P,Q)
if Size(P) <> Size(Q) then
return false;
fi;
return ForAll([1..Size(P)], i -> Size(P[i]) = Size(Q[i]));
end;;
Agreeable([ [1,2,3], [4,5] ], [[1,2], [3,4,5] ]);falseAgreeable([ [1,2,3], [4,5] ], [[1,2,3], [3,4,5] ]);falseAgreeable([ [1,2,3], [4,5],[5] ], [[1,2,3], [4,5] ]);falseAgreeable([ [1,2,3], [4,5] ], [[1,2,3], [4,5],[5] ]);falseAgreeable([ [1,2,3], [4,5] ], [[1,2,3], [4,5] ]);trueWhy is agreeable useful? For the following mini-lemma!
- Given two ordered partitions
PandQ, there exists a permutationpwhich mapsPtoQif and only ifPandQare agreeable.
One lemma is fairly easy to prove: If P and Q aren’t agreeable, then there can’t be any mapping from P to Q, as any image of P will be agreeable with P. If P and Q are agreeable, then we can easily construct a mapping from P to Q by imposing any ordering on the cells of P and Q, and mapping them pointwise.
We can use this to construct all the mappings of P to Q. We can also construct them more easily using the fact that they form a coset of the mappings of P to itself.
Now we have a giant pile of partition-related results, we can start using them to do interesting things! But first, we need to consider a series of ordered partitions, known as a partition stack.