> < ^ Date: Sun, 23 Nov 2003 15:31:29 +0100
> < ^ From: Dmitrii Pasechnik <dima@thi.informatik.uni-frankfurt.de >
< ^ Subject: Re: pairwise nonintersection graphs?

Dear GAP-Forum,

On Thu, Nov 20, 2003 at 09:40:57AM -0500, Drew Krause wrote:
> I would like to be able to do the following using GAP and the grape
> package. I need help in the proper way to formulate the problem in terms
> of the software:
>
> (1) Take the set of non-identical pairs (x,y) from a set of n elements.
> Two pairs would be connected if the intersection of its members was
> empty. For example. the pairs (1,3) and (4,2) would be connected, but
> (1,3) and (2,3) would not.
just do (after RequirePackage("grape")) the following:
ComplementGraph(JohnsonGraph(n,2));

>
> (2) Generalize the above to tuples of length greater than 2. For
> example, (1,3,4) and (2, 5, 6) would be connected since there is no
> intersection among the members.
for k being the size of the subsets:

g:=SymmetricGroup(n);;
Graph(g,Orbit(g,[1..k],OnSets),OnSets,                           
   function(x,y) return Size(Intersection(x,y))=0; end, true);

HTH,
Dmitrii

Dmitrii Pasechnik
http://www.thi.informatik.uni-frankfurt.de/~dima/

Miles-Receive-Header: reply


> < [top]