`part := [ Set([2,3,6]), Set([1]), Set([4,5]) ];`

`[ [ 2, 3, 6 ], [ 1 ], [ 4, 5 ] ]`

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

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:

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]\) .

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 ] ]`

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.

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.

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] ]);;
```

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`

:

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.

*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] ]);
```

`false`

Why is agreeable useful? For the following mini-lemma!

- Given two ordered partitions
`P`

and`Q`

, there exists a permutation`p`

which maps`P`

to`Q`

if and only if`P`

and`Q`

are 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*.