Shortly after we built the six factorizations of $K_6$, we created a graphic which was another version of $K_6$ with factorizations as vertices and factors labeling (coloring) edges. This was possible, since as we also demonstrated above, every pair of factorizations have a single factor in common, and each factor is contained in exactly two factorizations. This version of $K_6$ is “dual” to the original $K_6$, as we will describe in this section. We need to create again the factorizations from previous sections of this chapter.

xxxxxxxxxx

K6 = graphs.CompleteGraph(6)

vertices = K6.vertices()

edges = [Set(e) for e in K6.edges(labels=False)]

factors = SetPartitions(vertices,[2,2,2]).list()

factors = [Set(list(A)) for A in factors]

factor_graph = Graph([(f1, f2) for f1, f2 in Subsets(factors, 2) if f1.intersection(f2).cardinality() == 0])

factorizations = factor_graph.cliques_maximum()

factorizations = [Set(f) for f in factorizations]

Build a graph, $Q$, whose vertices are the factorizations of $K_6$, with two vertices adjacent if the factorizations have a factor in common. The code below is a bit overblown, as we expect this graph to be isomorphic to $K_6$. To emphasize the situation, we will label the vertices of $Q$ (factorizations) by using names, uppercase letters from the end of the alphabet.

xxxxxxxxxx

Q = Graph([(f1, f2) for f1, f2 in Subsets(factorizations, 2) if f1.intersection(f2).cardinality() == 1])

factorization_names = dict(zip(factorizations, [chr(i) for i in range(ord('U'), ord('a')+6)]))

Q.relabel(factorization_names)

Q.plot(layout='circular')

You can see it, but we will let Sage do the work for us.

xxxxxxxxxx

Q.is_isomorphic(graphs.CompleteGraph(6))

By construction, the factorizations of $K_6$ are the vertices of $Q$. The factors of $K_6$, by the discussion above, are in a bijective correspondence with the edges of $Q$ (pairs of factorizations). We illustrate these ideas with functions that accept the factorizations and factors of $K_6$ (respectively) and return the vertices and edges of $Q$. To emphasize the nature of the situation, the trivial function that takes factorizations to vertices will return the factorization names provided by the Python dictionary factorization_names. We test these functions exhaustively. Also, notice how the second function employs the first.

xxxxxxxxxx

def factorization2vertex(afactorization):

    '''Returns a vertex of the dual graph determined by a factorization of the original graph'''

    return factorization_names[afactorization]

[factorization2vertex(fz) for fz in factorizations]

xxxxxxxxxx

def factor2edge(afactor):

    '''Returns an edge of the dual graph determined by a factor of the original graph'''

    endpoints = [fz for fz in factorizations if afactor in fz]

    return Set([factorization2vertex(avertex) for avertex in endpoints])

[factor2edge(f) for f in factors]

Now we describe a natural bijection between edges of $K_6$ and factors of $Q$. Given an edge of $K_6$, there remain four vertices not incident to this edge. The subgraph induced by these four vertices (a complete graph on 4 vertices) contains three pairs of disjoint edges, which may be combined with the first edge to form the three edges of a factor of $K_6$. Each of these three factors of $K_6$ is then associated with an edge of $Q$. Since these three factors are not pairwise disjoint, no two of the factors can be in the same factorization. So the three factors determine three pairs of factorizations, and these six factorizations are different. Thus, these three pairs of factorizations form a factor in the graph $Q$. So we begin with an edge of $K_6$ and determine a factor of the dual, $Q$.

Here is the function, and the test.

xxxxxxxxxx

def edge2factor(anedge):

    '''Returns a factor of the dual graph determined by an edge of the original graph'''

    completions = [f for f in factors if anedge in f]

    return [factor2edge(f) for f in completions]

[edge2factor(e) for e in edges]

Finally, you might now expect a natural bijection between vertices of $K_6$ and factorizations of $Q$. We will not disappoint. Given a vertex of $K_6$, there are five edges incident to this vertex. No factor of $K_6$ can contain two of these edges, since all the edges have a vertex in common. Each edge determines a factor of $Q$ as above. These five factors of $Q$ are disjoint, for if not, an edge common to two factors of $Q$ would be associated with a factor of $K_6$ that contained two of the five original edges of $K_6$. So a vertex of $K_6$ determines five disjoint factors of $Q$, a factorization of the dual, $Q$.

xxxxxxxxxx

def vertex2factorization(avertex):

    '''Returns the factorization of the dual graph determined by a vertex of the original graph'''

    incident = [e for e in edges if avertex in e]

    return [edge2factor(e) for e in incident]

[vertex2factorization(v) for v in vertices]

So notice that we have computed the factors and factorizations of the dual graph $Q$ by exploiting properties of vertices, edges, factors and factorizations in $K_6$. This is in contrast to computing factors and factorizations of $Q$ with set partition routines, or maximal cliques in an appropriate graph. The following table summarizes what we mean by saying that $Q$ is the dual of $K_6$.

Cameron and van Lint state the following theorem.

So here $A$ is the set of six original vertices of $K_6$, and the “$n$ isomorphic objects” are the six factorizations of $K_6$. We saw in the section on group actions that each permutation of the vertex set of $K_6$ creates a permutation of the factorizations. While there is a one-to-one correspondence between vertices and factorizations, the correspondence is not trivial. This theorem can be explained several ways, but perhaps the most concise is the category-theoretic statement that

The category whose objects are $n$-element sets and whose morphisms are bijections between them has a non-trivial functor to itself if and only if $n=6$.