next | previous | forward | backward | up | top | index | toc | Macaulay2 website
EdgeIdeals :: randomHyperGraph

randomHyperGraph -- returns a random hypergraph

Synopsis

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 }}}
                            2   4   5     1   5     1   2   3   4
                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     2   3     1   2   4   5
                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).

See also

Ways to use randomHyperGraph :

For the programmer

The object randomHyperGraph is a method function with options.