[Nauty-list] Detecting isomorphic collections in the Boolean lattice
Kevin Gilbert
kev.gilbert at cdu.edu.au
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://mailman.anu.edu.au/mailman/private/nauty/attachments/20061128/fe4e54e4/attachment.html
More information about the Nauty
mailing list