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

Mathieu Dutour Mathieu.Dutour at ens.fr
Tue Nov 28 18:38:05 EST 2006


Hi,

one possibility, which you may consider is to use the GAP computer
algebra package and the OnSets action.

More precisely, the group Sym(n) acts on {0,1}^n. We list all 2^n
elements of {0,1}^n and make a permutation representation of Sym(n)
on 2^n elements. If all sets have the same size k, then of course
the representation acts only on n choose k elements.

The collections are thus encoded as subsets of {0,1}^n and the
isomorphism can be resolved by
g:=RepresentativeAction(TheGroup, TheSet1, TheSet2, OnSets);
The keypoint is that the OnSets action of GAP uses a backtrack search
method and is therefore rather efficient.

Sometimes this is faster than nauty. The reason is that we know the
relevant automorphism group and we do not need to have nauty compute
it.

The big drawback is that we cannot use this from a C program since
as far as I know there is no C library implementation of the relevant
algorithms.

  Mathieu



On Tue, Nov 28, 2006 at 11:01:21AM +0930, 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?
> 
> Thanks in advance for any assistance,
> 
> Kevin
> 
> -- 
> Kevin Gilbert
> 
> Lecturer in IT
> School of Information Technology
> Charles Darwin University
> NT 0909
> 
> CRICOS Registered Provider# 00300K
> 
> Ph:  (08) 8946 6282
> Fax: (08) 8946 6667
> Home page: http://informatics.cdu.edu.au/staff/kgilbert/
> 
> ==================================
> 
> Every new body of discovery is mathematical in form, because there is no other 
> guidance we can have - Charles Darwin



> _______________________________________________
> Nauty-list mailing list
> Nauty-list at cs.anu.edu.au
> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list


-- 
Mathieu Dutour Sikiric		Researcher in Mathematics
Telephone:.(+385)1 4571 237	and Computer Science
Cell Phone: (+385)9 19 36 30 80	Laboratory of satellite oceanography
E-mail: Mathieu.Dutour at ens.fr	Rudjer Boskovic Institute
http://www.liga.ens.fr/~dutour	Zagreb Croatia
skype name: mathieudutour




More information about the Nauty mailing list