# [Nauty] hypergraphs

Brendan McKay Brendan.McKay at anu.edu.au
Wed Jan 24 10:00:20 AEDT 2018

```Hi Susanne,

I'll assume you want simple hypergraphs (no two edges the same).

The quickest way for l=r+2 is to take the graphs on l vertices and
replace each edge e by its complement V-e (where V is the vertex set).

More generally, you can make hypergraphs using genbg.  Consider the left
side of the bipartite graph to be the vertices of the hypergraph, and
the right side of the bipartite graph to be the hyperedges.

For example, to make the simple 3-regular hypergraphs with 11 edges and
8 vertices:

%% genbg -d0:3 -D99:3 -z 8 11
>A genbg n=8+11 e=33:33 d=0:3 D=11:3 z
>Z 3826031 graphs generated in 20.87 sec

An example of the output is this graph:

0 : 8 9 10 11 12 13 14 15;
1 : 8 9 10 13 18;
2 : 8 11 12 16 18;
3 : 9 11 17;
4 : 10 14 15 17;
5 : 12 16 18;
6 : 13 15 16;
7 : 14 17;
8 : 0 1 2;
9 : 0 1 3;
10 : 0 1 4;
11 : 0 2 3;
12 : 0 2 5;
13 : 0 1 6;
14 : 0 4 7;
15 : 0 4 6;
16 : 2 5 6;
17 : 3 4 7;
18 : 1 2 5;

The neighbourhoods of vertices 8-18 are the hyperedges of the hypergraph.

If you want to allow repeated edges, remove "-z" and expect a lot more
graphs.

Cheers, Brendan.

On 24/1/18 5:11 am, Susanne Nieß wrote:
> Hi
>
>
> I am very glad about geng to make lists of graphs but I also need such
> lists of hypergraphs. My own attempts on writing programmes for that
> rely on nauty but seem clumsy and sluggish compared to geng. Do you
> have or know any software that could help me or give advice where to
> look for an algorithm? What I need are comprehensive lists of all
> r-uniform hypergraphs on l vertices for as many values of r and l as
> possible (the lists for l < r are trivial and the lists for l=r and
> l=r+1 are easy to make but to really make use of a number r I need at
> least a list for l=r+2).
>
>
> I look forward to hearing from you.
>
>
> Susanne.
>
> _______________________________________________
> Nauty mailing list
> Nauty at anu.edu.au
> http://mailman.anu.edu.au/mailman/listinfo/nauty

```