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

Tue Nov 28 15:01:05 EST 2006

Thanks for your prompt (very) reply. I will investigate the first part of your 
response re bipartite graphs. But I would like to follow-up on the second 
part of your reply.

I have created the Hasse graph of the n-cube and fed that into nauty and have 
tried the following two partitioning schemes:

1) Colouring 123, 124 one colour and all the other vertices another,
2) Colouring 123, 124 one colour, the rest of the sets on the same "level" 
another colour, then the remaining levels coloured with their own colour 
(thus using n+2 colours).

In both cases I have been unable to successfully interpret the output from 
nauty. For example, using colouring scheme (1) the two runs of nauty produce the following output.

before nauty:
		RUN 1				RUN 2
	set	lab	ptn		set	lab	ptn
	124	17	-1		134	19	-1
	125	18	0		135	20	0
	123	16	-1		123	16	-1
	134	19	-1		124	17	-1
	135	20	-1		125	18	-1
	145	21	-1		145	21	-1
	234	22	-1		234	22	-1
	235	23	-1		235	23	-1
	245	24	-1		245	24	-1
	345	25	-1		345	25	-1
	*	0	-1		*	0	-1
	1	1	-1		1	1	-1
	2	2	-1		2	2	-1
	3	3	-1		3	3	-1
	4	4	-1		4	4	-1
	5	5	-1		5	5	-1
	12	6	-1		12	6	-1
	13	7	-1		13	7	-1
	14	8	-1		14	8	-1
	15	9	-1		15	9	-1
	23	10	-1		23	10	-1
	24	11	-1		24	11	-1
	25	12	-1		25	12	-1
	34	13	-1		34	13	-1
	35	14	-1		35	14	-1
	45	15	-1		45	15	-1
	1234	26	-1		1234	26	-1
	1235	27	-1		1235	27	-1
	1245	28	-1		1245	28	-1
	1345	29	-1		1345	29	-1
	2345	30	-1		2345	30	-1
	12345	31	0		12345	31	0
after nauty:
	RUN 1			RUN 2
	lab	orbit		lab	orbit
	17	0		19	0
	18	1		20	1
	1	1		1	2
	24	3		25	1
	4	4		4	4
	21	4		21	4
	2	6		3	0
	16	0		16	7
	22	8		22	8
	23	8		23	8
	4	0		4	0
	19	8		17	11
	20	8		18	11
	5	13		5	8
	3	13		2	8
	25	0		24	0
	13	1		11	1
	14	17		12	4
	0	17		0	4
	7	4		6	19
	15	4		15	19
	29	1		28	1
	30	4		30	4
	10	4		10	4
	8	1		8	2
	9	3		9	1
	11	8		13	8
	12	8		14	8
	27	6		27	0
	26	0		26	7
	6	0		7	0
	28	1		29	1
I have not been able to make any sense out of the nauty output. Note that in both runs, getcanon was set to true.

Again, thanks in advance for any assistance.

Cheers,

Kevin
On Tuesday 28 November 2006 11:20, you opined:
> 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

-- 
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://dcsmail.anu.edu.au/pipermail/nauty-list/attachments/20061128/fe4e54e4/attachment.htm