# randomHyperGraph -- returns a random hypergraph

## Synopsis

• Usage:
H = randomHyperGraph(R,D)
• Inputs:
• R, , 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 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 }}} 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).

## Ways to use randomHyperGraph :

• "randomHyperGraph(PolynomialRing,List)"

## For the programmer

The object randomHyperGraph is .