http://openproblemgarden.org/op/rysers_conjecture Comments for "Ryser's conjecture" en http://openproblemgarden.org/op/rysers_conjecture <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/ryser">Ryser</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/hypergraphs">Hypergraphs</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; Let <img class="teximage" src="/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png" alt="$ H $" /> be an <img class="teximage" src="/files/tex/535dee6c3b72bcc4d571239ed00be162ee1e6fbe.png" alt="$ r $" />-<a href="http://en.wikipedia.org/wiki/hypergraph">uniform</a> <img class="teximage" src="/files/tex/535dee6c3b72bcc4d571239ed00be162ee1e6fbe.png" alt="$ r $" />-partite hypergraph. If <img class="teximage" src="/files/tex/84ef96eb1030eaa1447d7a3c9ce8be567b7eccc8.png" alt="$ \nu $" /> is the maximum number of pairwise disjoint edges in <img class="teximage" src="/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png" alt="$ H $" />, and <img class="teximage" src="/files/tex/706065ef4c2d4b462dff91b9ad9fc69d846c15dc.png" alt="$ \tau $" /> is the size of the smallest set of vertices which meets every edge, then <img class="teximage" src="/files/tex/03ec477958b1e8cdfcb12ec5ef3d32014472a61d.png" alt="$ \tau \le (r-1) \nu $" />. </div> </tr></td> </table> </td> </tr> </table> Ryser, Herbert J. hypergraph matching packing Graph Theory Hypergraphs http://openproblemgarden.org/op/rysers_conjecture#comment Mon, 19 Mar 2007 01:11:18 +0100 mdevos 165 at http://openproblemgarden.org