Graph Canonization & "set of isomorphism"

Question

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

Answer 1

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!)

Answer 2

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

Gerhard "Ask Me About System Design" Paseman, 2011.05.13