Graph Canonization & "set of isomorphism"

Hello,

I am new to MathOverflow as I was referred. Furthermore, I am NOT a mathematician so if you can please take that into consideration when formulating your answers. 

I am interested in covering designs as I have written an efficient algorithm for finding non-isomorphic covering designs. I have been able to write my own algorithm for testing for isomorphism insofar as for the relabeling of the elements, but I was told that just relabeling the elements is not enough and that I need to test for the “set of isomorphism”. Here is what I was told and I quote:

“The set of isomorphisms consist of relabeling elements and permuting the order of the blocks (and permuting the elements in the blocks if you see them as lists rather than sets).

First, you can "normalize" a design by sorting the elements in each block in increasing order and then sort the set of blocks lexicographically.

Second, in order to see if a design A is isomorphic to a design B you can normalize A and then apply every possible permutation to the elements in B, normalize each design you got in this was, and then see if any of them is the same as the normalized version of A.

The normalization I am referring to is the canonical form of the design.”

I think that in order for me to fully understand the whole process of the “set of isomorphism” it would be within the context of an example so I will use the covering design C(10,6,3) = 10 blocks for my example and call the first Design A and the second Design B for illustrative purposes.

Design A

1 2 3 4 6 7

1 2 3 5 7 10

1 2 3 8 9 10

1 2 4 6 8 10

1 3 4 5 6 9

1 4 5 7 8 9

2 4 5 6 9 10

2 5 6 7 8 9

3 4 5 7 8 10

3 6 7 8 9 10

Design B

1 2 3 4 6 7

1 2 3 5 8 10

1 2 3 7 9 10

1 2 4 6 8 10

2 3 4 5 6 9

1 4 5 7 8 9

1 4 5 6 9 10

2 5 6 7 8 9

3 4 5 7 8 10

3 6 7 8 9 10

So I will proceed with the first part that is “normalizing” Design A.

The elements are already in increasing order in each block so now I just have to sort the set of blocks lexicographically.

Is this how Design A would be sorted lexicographically?

Design A (36) Normalized (lexicographically sorted)

123467

134569

145789

256789

1235710

1238910

1246810

2456910

3457810

3678910

Now to the second part and assuming I “normalized” Design A properly, I now have to apply every possible permutation to the elements in Design B.

This is where I am really confused!!! What does it mean to “apply every possible permutation to the elements in Design B”???

Does it mean to permute elements within each block only? Or even to permute elements across any block? Or does it have anything to do with relabeling elements at all? How exactly are the elements in Design B permuted so that when they are normalized they are the same as the normalized Design A because I was told that Design A and Design B are isomorphic? Can you show me the step by step process?

An answer would be really appreciated?

Thanks Roy Gourgi

• "Apply every possible permutation" means that for each of the 3,628,800 permutations of the set {1,2,3,...,10} (i.e., each one-to-oone mapping of this set onto itself) you should apply that function to every entry in your entire Design B. This is what's involved in the definition of isomorphism. Getting an algorithm that works reasonably fast on reasonably large designs is a more difficult matter. This is not a research-level question, so I'm voting to close. May 13, 2011 at 19:13
• Let's say one permutation relabeled element 1 with element 10 then Design B normalized would be: 134578 136789 234569 256789 1235810 1237910 1246810 1456910 2346710 4578910 Is this right? Then I would check to see if each of the normalized blocks in Design B are exactly the same as in Design B. The first block in Design B is 134578 but no corresponding block in Design A, therefore this permutation of Element 1 with Element 10 does not work. And this would be done for all the 3,628,800 permutations. IS THIS RIGHT??? I am trying to make sure I understand the mechanics of it! Thx May 14, 2011 at 17:15
• Sorry that should have been: Then I would check to see if each of the normalized blocks in Design B are exactly the same as in Design A. May 14, 2011 at 17:18

For the sizes you have presented, this is an easy problem to solve in practice.

Convert your design into a bipartite graph, with vertices being the points and the blocks of the design and making a "point vertex" adjacent to a "block vertex" if the point is in the block.

Run a graph canonical labelling program - I recommend Brendan McKay's "nauty" program (Google 'bdm nauty page") - and then two designs are isomorphic if and only if the canonically labelled graphs are the same. (If you have designs with the same number of points as blocks, you will want to use the feature of nauty that permits you to partition the vertices of a graph - this avoids points getting mixed up with blocks!)

This question is more suited to math.stackexchange; see the MathOverflow FAQ for a list of alternative sites to accept the question. However, there is some visualization which may be useful, so I include it as an answer.

Consider a set system in which every set has size two. It will represent some symmetric nonreflexive relation (e.g. who has shaken hands with someone else at a gathering, perhaps useful in tracking down the source of a cold?). While labels (on the points) are sometimes important, to see if two such systems are isomorphic, one needs to provide a map between them such that the map (say it is called f() ) is one-to-one and onto the underlying point sets, and such that {a,b} is in one set system if and only if {f(a),f(b)} is in the other. This is the graph isomorphism problem, and while there are programs that will check quickly if two small graphs are isomorphic, it is not known that one can do such checks quickly in general. (cf "Is Graph Isomorphism in P or NP ?")

Your problem is for hypergraphs, an extension which includes graphs as a special case. I can imagine your algorithm does well on small examples, and by some processing you can avoid checking all possible maps from one vertex-set of a hypergraph to another, but to check that two sets systems are isomorphic or not, you either need to find the isomorphism, or prove it does not exist. Right now computers are not clever enough to prove non-existence through any means other than (essentially) exhaustive elimination, i.e. by checking all the possible maps and showing that they are not isomorphisms. If your underlying point set is {1,...,10} for set system A and {1,...,10} for set system B, then you have to check all one-to-one onto maps (permutations) from one set to the other. If you have ordered the blocks in set system A, such a map may not necessarily respect that order (an isomorphism between A and B may map block 1 in A to block 7 in B, depending on how things are ordered).

(One can talk about graph and hypergraph invariants, and other means to rule out two objects being isomorphic, but I want to emphasize the point that there is no simple or easy way to do it, rather than get bogged down explaining how programs like nauty work well in practice.)