randomHyperGraph -- returns a random hypergraph

Synopsis

Usage:

H = randomHyperGraph(R,D)
Inputs:
- R, a polynomial ring, which gives the vertex set of H
- D, a list, of integers that are the cardinalities of the edges of H
Optional inputs:
- BranchLimit => ..., default value 3, limit recursive branching in randomHyperGraph
- TimeLimit => ..., default value 5, limit the running time of randomHyperGraph
Outputs:
- H, a hypergraph, a hypergraph with edges E_i each of size D_i. Returns null if none can be found.

Description

This method is not guaranteed to return a HyperGraph, even if one exists with the given edge sizes. This method searches for a hypergraph with the given edge sizes using a random recursive algorithm. Limits can be placed on the both number of recursive steps taken (see BranchLimit) and on the time taken (see TimeLimit). The method will return null if it cannot find a hypergraph within the branch and time limits.

i1 : R = QQ[x_1..x_5];

i2 : randomHyperGraph(R,{3,2,4})

i3 : randomHyperGraph(R,{3,2,4})

o3 = HyperGraph{"edges" => {{x , x , x }, {x , x }, {x , x , x , x }}}
                              1   4   5     3   4     1   2   3   5
                "ring" => R
                "vertices" => {x , x , x , x , x }
                                1   2   3   4   5

o3 : HyperGraph

i4 : randomHyperGraph(R,{3,2,4})

o4 = HyperGraph{"edges" => {{x , x , x }, {x , x }, {x , x , x , x }}}
                              1   3   5     4   5     1   2   3   4
                "ring" => R
                "vertices" => {x , x , x , x , x }
                                1   2   3   4   5

o4 : HyperGraph

i5 : randomHyperGraph(R,{4,4,2,2}) -- impossible, returns null when time/branch limit reached

The randomHyperGraph method will return null immediately if the sizes of the edges fail to pass the LYM-inequality: $1/(n choose D_1) + 1/(n choose D_2) + ... + 1/(n choose D_m) \leq 1$ where $n$ is the number of variables in R and $m$ is the length of D. Note that even if D passes this inequality, it is not necessarily true that there is some hypergraph with edge sizes given by D. See D. Lubell's "A short proof of Sperner's lemma," J. Combin. Theory, 1:299 (1966).

Ways to use randomHyperGraph:

randomHyperGraph(PolynomialRing,List)

For the programmer

The object randomHyperGraph is a method function with options.

randomHyperGraph -- returns a random hypergraph

Synopsis

Description

See also

Ways to use randomHyperGraph:

For the programmer