Ordered Partitions

This chapter 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 chapter contains no deep mathematics, but does dive into some algorithm details.

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 union of the cells is \(\{1, \ldots, 6\}\).

Given an ordered partition, we can ask for the cell of some \(o \in \Omega\), which returns the index of the cell containing \(o\).

Explicit representation

How can we represent an ordered partition in GAP? There are a few options, with different tradeoffs. The easiest is as a list of sets. We will call this the explicit representation:

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

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

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 the explicit 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. So let us consider a second representation, the simple indicator representation. This maps each value to the cell containing it. For example, part from above is represented by the list l := [2,1,1,3,3,1]. The simple indicator and explicit representations are linked by \(l[i] = j \leftrightarrow i \in \mathit{part}[j]\).

Complex indicator representation

Our final representation is the complex indicator representation. This is like the simple indicator representation, except we allow the array to contain any values, not just 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 ordering is, but it must exist. GAP provides a complete ordering on (almost) all objects, where for example all integers are less than all strings. By design, all simple indicator representations are also complex indicator representations.

Here are a couple of GAP functions which map between the explicit and simple indicator representations. First, explicit to simple indicator:

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 back the other way — from any indicator representation to explicit. This function first gathers the labels used, then uses Position to find the location of each value in the ordering.

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 two different representations? The indicator representation feels less mathematically nice, particularly the complex indicator. The reason we use it is that it makes one of our most important operations easy to express: refinement.

Given two ordered partitions \(P\) and \(Q\) of the same set \(\{1, \ldots, n\}\), \(Q\) is a refinement of \(P\) if every cell of \(Q\) is contained in a cell of \(P\). Equivalently, \(Q\) can be built by splitting cells of \(P\).

Important aside. There is a stricter definition of refinement which imposes an order on the cells of \(Q\): if \(P\) has \(j\) cells, it requires \(\forall i \in \{1, \ldots, j\}.\, Q[i] \subseteq P[i]\). We will not use that here, but it may come up in later chapters.

Let’s consider a couple of ways of taking a partition and producing a refinement of it. Both will be used repeatedly in partition backtrack and graph isomorphism.

Fixing a single point

Consider a partition in explicit format — our running example part := [ [2,3,6], [1], [4,5] ];. We want to take this and produce a new partition where a single value has been extracted and 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 — only their contents.

The easiest way to fix a single point is to switch to indicator representation and change the value. All we need to do is give our point a label 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 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. This is easy to implement with the complex indicator representation, as we can simply label each value with the pair of its labels in P and Q. We calculate the meet of 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 our searches, we will often want to look at all the permutations which map an ordered partition to itself, or one ordered partition to another. Two important basic results in this area (we won’t prove these here, but they are not complicated):

• Given an ordered partition \(P\), the set of permutations \(p\) such that \(P^p = P\) is generated by the direct product of the symmetric groups on each cell of \(P\).

GAP already uses this internally to quickly calculate the stabiliser of a 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 they have the same number of cells, and for all i, the size of P[i] equals 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

Agreeable([ [1,2,3], [4,5] ], [[1,2,3], [3,4,5] ]);

false

Agreeable([ [1,2,3], [4,5],[5] ], [[1,2,3], [4,5] ]);

false

Agreeable([ [1,2,3], [4,5] ], [[1,2,3], [4,5],[5] ]);

false

Agreeable([ [1,2,3], [4,5] ], [[1,2,3], [4,5] ]);

true

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 direction is easy: if P and Q aren’t agreeable, then there is no mapping from P to Q, as any image of P is agreeable with P. In the other direction, if P and Q are agreeable, then we can construct a mapping by imposing any ordering on the cells of P and Q and mapping pointwise.

We can use this to construct all the mappings from P to Q. We can also construct them using the fact that they form a coset of the mappings of P to itself.

With all this partition machinery, we can start using it to do interesting things — starting with graph isomorphism.