[Nauty-list] Detecting isomorphic collections in the Boolean lattice

[Gordon Royle]

On 28/11/2006, at 9:31 AM, Kevin Gilbert wrote:

> Hi,
>
> I am trying to use nauty test whether two collections of sets from  
> the Boolean
> lattice are isomorphic. For example, I want some way for nauty to  
> tell me
> that the collections 123, 124 and 134, 135 are isomorphic.
>
> I have tried various colouring schemes, canonical labelling & etc  
> without any
> success.
>
> So I am left with these questions: (1) Can nauty be used in this  
> fashion? (2)
> If so, how?


Yes.. and in a few different ways...

In your case, if you are working with the full boolean lattice, then  
you can just treat your collections as the "blocks" of a design-type  
thing.

Create a bipartite graph with one vertex for each point  and one  
vertex for each block, where a "block"-vertex is adjacent to a  
"point"-vertex if the block contains the point. For your example, we  
would have two 7-vertex graphs - in the first graph vertex 5 would be  
adjacent to 0,1,2 and vertex 6 adjacent to 0,1,3, while in the second  
graph vertex 5 would be adjacent to 0,2,3, and vertex 6 adjacent to  
0,2,4.   [I have renamed the points so they start at 0].

Then just compute the canonical labelling of each graph and if they  
are the same, then the collections are the same.

[I have glossed over / finessed / lied to you about one detail - for  
complete safety you should ensure that the point-vertices and the  
block-vertices cannot get "mixed up" by nauty by using the lab/ptn  
feature to compute the canonical labelling of the PARTITIONED graph  
where the points form one cell and the blocks another cell. Otherwise  
you can mistakenly mix up a set with its dual, although this will  
only happen in special circumstances]


Alternatively, you could create a graph consisting of the entire  
boolean lattice (aka n-cube) and then compute the canonical labelling  
of the partitioned graph where your chosen set (mapped to vertices in  
the graph) forms one cell and the remaining vertices the other cell.

Hope this helps..

gordon