http://openproblemgarden.org/op/compatible_matching_conjecture Comments for "Compatible Matching Conjecture" en http://openproblemgarden.org/op/compatible_matching_conjecture <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/wood_david_r">Wood</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/topological_graph_theory">Topological G.T.</a> » <a href="/category/drawings_0">Drawings</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <p>For an even set <img class="teximage" src="/files/tex/d2b76a0ee5465d3e3ecc846c8e3d632edd8b2bbf.png" alt="$ S $" /> of points in the plane, a <em>perfect matching of <img class="teximage" src="/files/tex/d2b76a0ee5465d3e3ecc846c8e3d632edd8b2bbf.png" alt="$ S $" /></em> is a collection of nonintersecting segments such that every point of <img class="teximage" src="/files/tex/d2b76a0ee5465d3e3ecc846c8e3d632edd8b2bbf.png" alt="$ S $" /> is an end of exactly one of the segments. </p> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; Let <img class="teximage" src="/files/tex/d2b76a0ee5465d3e3ecc846c8e3d632edd8b2bbf.png" alt="$ S $" /> be a set of points in the plane in general position such that <img class="teximage" src="/files/tex/eece442959b168eaef20d3ef50a1ad89447ca608.png" alt="$ |S| $" /> is divisible by 4. Then for every perfect matching <img class="teximage" src="/files/tex/3f02401f624e31ef8679d3c3628c1f310058f388.png" alt="$ M $" /> of <img class="teximage" src="/files/tex/d2b76a0ee5465d3e3ecc846c8e3d632edd8b2bbf.png" alt="$ S $" /> there is another perfect matching, <img class="teximage" src="/files/tex/e178f13e28934a284e7c8f31e0187aee6ebdf650.png" alt="$ N $" />, of <img class="teximage" src="/files/tex/d2b76a0ee5465d3e3ecc846c8e3d632edd8b2bbf.png" alt="$ S $" /> such that no segment of <img class="teximage" src="/files/tex/3f02401f624e31ef8679d3c3628c1f310058f388.png" alt="$ M $" /> crosses a segment of <img class="teximage" src="/files/tex/e178f13e28934a284e7c8f31e0187aee6ebdf650.png" alt="$ N $" />. </div> </tr></td> </table> </td> </tr> </table> Wood, David R. geometric graphs matchings Graph Theory Topological Graph Theory Drawings http://openproblemgarden.org/op/compatible_matching_conjecture#comment Fri, 01 Aug 2008 00:34:24 +0200 Robert Samal 1817 at http://openproblemgarden.org