<?xml version="1.0" encoding="utf-8" ?> <!-- for emacs: -*- coding: utf-8 -*- --> <!-- Apache may like this line in the file .htaccess: AddCharset utf-8 .html --> <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1 plus MathML 2.0 plus SVG 1.1//EN" "http://www.w3.org/2002/04/xhtml-math-svg/xhtml-math-svg-flat.dtd" > <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en"> <head><title>randomHyperGraph -- returns a random hypergraph</title> <link rel="stylesheet" type="text/css" href="../../../../Macaulay2/Style/doc.css"/> </head> <body> <table class="buttons"> <tr> <td><div><a href="_random__Hyper__Graph_lp..._cm_sp__Branch__Limit_sp_eq_gt_sp..._rp.html">next</a> | <a href="_random__Graph.html">previous</a> | <a href="_random__Hyper__Graph_lp..._cm_sp__Branch__Limit_sp_eq_gt_sp..._rp.html">forward</a> | <a href="_random__Graph.html">backward</a> | up | <a href="index.html">top</a> | <a href="master.html">index</a> | <a href="toc.html">toc</a> | <a href="http://www.math.uiuc.edu/Macaulay2/">Macaulay2 web site</a></div> </td> </tr> </table> <hr/> <div><h1>randomHyperGraph -- returns a random hypergraph</h1> <div class="single"><h2>Synopsis</h2> <ul><li><div class="list"><dl class="element"><dt class="heading">Usage: </dt><dd class="value"><div><tt>H = randomHyperGraph(R,D)</tt></div> </dd></dl> </div> </li> <li><div class="single">Inputs:<ul><li><span><tt>R</tt>, <span>a <a href="../../Macaulay2Doc/html/___Polynomial__Ring.html">polynomial ring</a></span>, which gives the vertex set of <tt>H</tt></span></li> <li><span><tt>D</tt>, <span>a <a href="../../Macaulay2Doc/html/___List.html">list</a></span>, of integers that are the cardinalities of the edges of <tt>H</tt></span></li> </ul> </div> </li> <li><div class="single">Outputs:<ul><li><span><tt>H</tt>, <span>a <a href="___Hyper__Graph.html">hypergraph</a></span>, a hypergraph with edges <tt>E<sub>i</sub></tt> each of size <tt>D<sub>i</sub></tt>. Returns <tt>null</tt> if none can be found.</span></li> </ul> </div> </li> <li><div class="single"><a href="../../Macaulay2Doc/html/_using_spfunctions_spwith_spoptional_spinputs.html">Optional inputs</a>:<ul><li><span><a href="_random__Hyper__Graph_lp..._cm_sp__Branch__Limit_sp_eq_gt_sp..._rp.html">BranchLimit => ...</a>, -- limit recursive branching in randomHyperGraph</span></li> <li><span><a href="_random__Hyper__Graph_lp..._cm_sp__Time__Limit_sp_eq_gt_sp..._rp.html">TimeLimit => ...</a>, -- limit the running time of randomHyperGraph</span></li> </ul> </div> </li> </ul> </div> <div class="single"><h2>Description</h2> <div><div>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 <a href="___Branch__Limit.html" title="optional argument for randomHyperGraph">BranchLimit</a>) and on the time taken (see <a href="___Time__Limit.html" title="optional argument for randomHyperGraph">TimeLimit</a>). The method will return null if it cannot find a hypergraph within the branch and time limits.</div> <table class="examples"><tr><td><pre>i1 : R = QQ[x_1..x_5];</pre> </td></tr> <tr><td><pre>i2 : randomHyperGraph(R,{3,2,4}) o2 = HyperGraph{edges => {{x , x , x }, {x , x }, {x , x , x , x }}} 1 4 3 1 5 5 3 2 4 ring => R vertices => {x , x , x , x , x } 1 2 3 4 5 o2 : HyperGraph</pre> </td></tr> <tr><td><pre>i3 : randomHyperGraph(R,{3,2,4})</pre> </td></tr> <tr><td><pre>i4 : randomHyperGraph(R,{3,2,4}) o4 = HyperGraph{edges => {{x , x , x }, {x , x }, {x , x , x , x }}} 2 1 3 4 1 3 5 2 4 ring => R vertices => {x , x , x , x , x } 1 2 3 4 5 o4 : HyperGraph</pre> </td></tr> <tr><td><pre>i5 : randomHyperGraph(R,{4,4,2,2}) -- impossible, returns null when time/branch limit reached</pre> </td></tr> </table> <div>The <tt>randomHyperGraph</tt> method will return null immediately if the sizes of the edges fail to pass the LYM-inequality: <i>1/(n choose D<sub>1</sub>) + 1/(n choose D<sub>2</sub>) + ... + 1/(n choose D<sub>m</sub>) ≤1</i> where <i>n</i> is the number of variables in <tt>R</tt> and <i>m</i> is the length of <tt>D</tt>. Note that even if <tt>D</tt> passes this inequality, it is not necessarily true that there is some hypergraph with edge sizes given by <tt>D</tt>. See D. Lubell’s "A short proof of Sperner’s lemma," J. Combin. Theory, 1:299 (1966).</div> </div> </div> <div class="single"><h2>See also</h2> <ul><li><span><a href="_random__Graph.html" title="returns a random graph">randomGraph</a> -- returns a random graph</span></li> <li><span><a href="_random__Uniform__Hyper__Graph.html" title="returns a random uniform hypergraph">randomUniformHyperGraph</a> -- returns a random uniform hypergraph</span></li> <li><span><a href="___Branch__Limit.html" title="optional argument for randomHyperGraph">BranchLimit</a> -- optional argument for randomHyperGraph</span></li> <li><span><a href="___Time__Limit.html" title="optional argument for randomHyperGraph">TimeLimit</a> -- optional argument for randomHyperGraph</span></li> <li><span><a href="___Constructor_sp__Overview.html" title="a summary of the many ways of making graphs and hypergraphs">Constructor Overview</a> -- a summary of the many ways of making graphs and hypergraphs</span></li> </ul> </div> <div class="waystouse"><h2>Ways to use <tt>randomHyperGraph</tt> :</h2> <ul><li>randomHyperGraph(PolynomialRing,List)</li> </ul> </div> </div> </body> </html>