http://openproblemgarden.org/op/strong_matchings_and_covers Comments for "Strong matchings and covers" en http://openproblemgarden.org/op/strong_matchings_and_covers <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/aharoni">Aharoni</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/infinite_graphs">Infinite Graphs</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <p>Let <img class="teximage" src="/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png" alt="$ H $" /> be a <a href="http://en.wikipedia.org/wiki/hypergraph">hypergraph</a>. A <em>strongly maximal</em> matching is a matching <img class="teximage" src="/files/tex/f281852be91f04903c1c524e853514c5807aa8b1.png" alt="$ F \subseteq E(H) $" /> so that <img class="teximage" src="/files/tex/0d2ab758312fe99c5eae0e6845ebf4b48e5f1aa8.png" alt="$ |F&#039; \setminus F| \le |F \setminus F&#039;| $" /> for every matching <img class="teximage" src="/files/tex/95a367a6e6efb31c15edd847865456f2290f58ae.png" alt="$ F&#039; $" />. A <em>strongly minimal</em> cover is a (vertex) cover <img class="teximage" src="/files/tex/9e6203081b70bf001f601e6923e4d70af31c5572.png" alt="$ X \subseteq V(H) $" /> so that <img class="teximage" src="/files/tex/b9d78c2958a7d402bc3811d2934c852dbf15a60c.png" alt="$ |X&#039; \setminus X| \ge |X \setminus X&#039;| $" /> for every cover <img class="teximage" src="/files/tex/f830c68e26d2437b96e61d53c71295413d1097f3.png" alt="$ X&#039; $" />. </p> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; If <img class="teximage" src="/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png" alt="$ H $" /> is a (possibly infinite) hypergraph in which all edges have size <img class="teximage" src="/files/tex/26d614fff037e5976f481eab5b4e36c487e120ac.png" alt="$ \le k $" /> for some integer <img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" />, then <img class="teximage" src="/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png" alt="$ H $" /> has a strongly maximal matching and a strongly minimal cover. </div> </tr></td> </table> </td> </tr> </table> Aharoni, Ron cover infinite graph matching Graph Theory Infinite Graphs http://openproblemgarden.org/op/strong_matchings_and_covers#comment Tue, 23 Oct 2007 05:00:44 +0200 mdevos 690 at http://openproblemgarden.org