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

definitionof isomorphism. Getting analgorithmthat 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. $\endgroup$