Hypergraph generators¶
This module implements generators of hypergraphs. All hypergraphs can be built
through the hypergraphs
object. For instance, to build a complete 3uniform
hypergraph on 5 points, one can do:
sage: H = hypergraphs.CompleteUniform(5, 3)
To enumerate hypergraphs with certain properties up to isomorphism, one can use
method nauty()
, which calls Brendan McKay’s Nauty
(http://cs.anu.edu.au/~bdm/nauty/):
sage: list(hypergraphs.nauty(2, 2, connected=True))
[((0,), (0, 1))]
This module contains the following hypergraph generators
nauty() 
Enumerate hypergraphs up to isomorphism using Nauty. 
CompleteUniform() 
Return the complete \(k\)uniform hypergraph on \(n\) points. 
UniformRandomUniform() 
Return a uniformly sampled \(k\)uniform hypergraph on \(n\) points with \(m\) hyperedges. 
Functions and methods¶

class
sage.graphs.hypergraph_generators.
HypergraphGenerators
¶ Bases:
object
A class consisting of constructors for common hypergraphs.

BinomialRandomUniform
(n, k, p)¶ Return a random \(k\)uniform hypergraph on \(n\) points, in which each edge is inserted independently with probability \(p\).
n
– number of nodes of the graphk
– uniformityp
– probability of an edge
EXAMPLES:
sage: hypergraphs.BinomialRandomUniform(50, 3, 1).num_blocks() 19600 sage: hypergraphs.BinomialRandomUniform(50, 3, 0).num_blocks() 0

CompleteUniform
(n, k)¶ Return the complete \(k\)uniform hypergraph on \(n\) points.
INPUT:
k,n
– nonnegative integers with \(k\leq n\)
EXAMPLES:
sage: h = hypergraphs.CompleteUniform(5, 2); h Incidence structure with 5 points and 10 blocks sage: len(h.packing()) 2

UniformRandomUniform
(n, k, m)¶ Return a uniformly sampled \(k\)uniform hypergraph on \(n\) points with \(m\) hyperedges.
n
– number of nodes of the graphk
– uniformitym
– number of edges
EXAMPLES:
sage: H = hypergraphs.UniformRandomUniform(52, 3, 17) sage: H Incidence structure with 52 points and 17 blocks sage: H.is_connected() False

nauty
(number_of_sets, number_of_vertices, multiple_sets=False, vertex_min_degree=None, vertex_max_degree=None, set_max_size=None, set_min_size=None, regular=False, uniform=False, max_intersection=None, connected=False, debug=False, options='')¶ Enumerate hypergraphs up to isomorphism using Nauty.
INPUT:
number_of_sets
,number_of_vertices
– integers.multiple_sets
– boolean (default:False
); whether to allow several sets of the hypergraph to be equal.vertex_min_degree
,vertex_max_degree
– integers (default:None
); define the maximum and minimum degree of an element from the ground set (i.e. the number of sets which contain it).set_min_size
,set_max_size
– integers (default:None
); define the maximum and minimum size of a set.regular
– integers (default:False
); if set to an integer value \(k\), requires the hypergraphs to be \(k\)regular. It is actually a shortcut for the corresponding min/max values.uniform
– integers (default:False
); if set to an integer value \(k\), requires the hypergraphs to be \(k\)uniform. It is actually a shortcut for the corresponding min/max values.max_intersection
– integers (default:None
); constraints the maximum cardinality of the intersection of two sets fro the hypergraphs.connected
– boolean (default:False
); whether to require the hypergraphs to be connected.debug
– boolean (default:False
); ifTrue
the first line of genbg’s output to standard error is captured and the first call to the generator’snext()
function will return this line as a string. A line leading with “>A” indicates a successful initiation of the program with some information on the arguments, while a line beginning with “>E” indicates an error with the input.options
– string (default:""
) – anything else that should be forwarded as input to Nauty’s genbg. See its documentation for more information : http://cs.anu.edu.au/~bdm/nauty/.Note
For genbg the first class elements are vertices, and second class elements are the hypergraph’s sets.
OUTPUT:
A tuple of tuples.
EXAMPLES:
Small hypergraphs:
sage: list(hypergraphs.nauty(4, 2)) [((), (0,), (1,), (0, 1))]
Only connected ones:
sage: list(hypergraphs.nauty(2, 2, connected=True)) [((0,), (0, 1))]
Nonempty sets only:
sage: list(hypergraphs.nauty(3, 2, set_min_size=1)) [((0,), (1,), (0, 1))]
The Fano Plane, as the only 3uniform hypergraph with 7 sets and 7 vertices:
sage: fano = next(hypergraphs.nauty(7, 7, uniform=3, max_intersection=1)) sage: print(fano) ((0, 1, 2), (0, 3, 4), (0, 5, 6), (1, 3, 5), (2, 4, 5), (2, 3, 6), (1, 4, 6))
The Fano Plane, as the only 3regular hypergraph with 7 sets and 7 vertices:
sage: fano = next(hypergraphs.nauty(7, 7, regular=3, max_intersection=1)) sage: print(fano) ((0, 1, 2), (0, 3, 4), (0, 5, 6), (1, 3, 5), (2, 4, 5), (2, 3, 6), (1, 4, 6))
