http://openproblemgarden.org/op/random_stable_roommates Comments for "Random stable roommates" en http://openproblemgarden.org/op/random_stable_roommates <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/mertens_stephan">Mertens</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/basic_graph_theory">Basic G.T.</a> » <a href="/category/matchings_0">Matchings</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; The probability that a random instance of the stable roommates problem on <img class="teximage" src="/files/tex/9d83db49a5d584edf4769392d3727c2df30f50c1.png" alt="$ n \in 2{\mathbb N} $" /> people admits a solution is <img class="teximage" src="/files/tex/7d356e001ed3a6d5303d583183ae3cbba921cbec.png" alt="$ \Theta( n ^{-1/4} ) $" />. </div> </tr></td> </table> </td> </tr> </table> Mertens, Stephan stable marriage stable roommates Graph Theory Basic Graph Theory Matchings http://openproblemgarden.org/op/random_stable_roommates#comment Tue, 26 Feb 2008 05:13:37 +0100 mdevos 743 at http://openproblemgarden.org