next | previous | forward | backward | up | top | index | toc | Macaulay2 web site

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})

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

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

o3 = HyperGraph{edges => {{x , x , x }, {x , x }, {x , x , x , x }}}
                            2   1   3     3   5     5   4   2   1
                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 }}}
                            5   4   1     5   2     1   2   4   3
                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 D1) + 1/(n choose D2) + ... + 1/(n choose Dm) ≤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 :