http://openproblemgarden.org/op/the_crossing_number_of_the_hypercube Comments for "The Crossing Number of the Hypercube" en http://openproblemgarden.org/op/the_crossing_number_of_the_hypercube#comment-951 <p>I came accross a paper <a href="http://dx.doi.org/10.1002/jgt.20330">Faria, Herrera de Figueiredo, Sykora, Vrto: An improved upper bound on the crossing number of the hypercube</a> that proves half of this, getting the correct upper bound.</p> Fri, 18 Jul 2008 16:46:21 +0200 Robert Samal comment 951 at http://openproblemgarden.org http://openproblemgarden.org/op/the_crossing_number_of_the_hypercube <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/erdos">Erdos</a>; <a href="/category/guy_richard_k">Guy</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/crossing_numbers">Crossing numbers</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <p>The crossing number <img class="teximage" src="/files/tex/1c88c74b39c3c8b388e8af0eb6b815eaa7a993c3.png" alt="$ cr(G) $" /> of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> is the minimum number of crossings in all drawings of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> in the plane.</p> <p>The <img class="teximage" src="/files/tex/aeba4a4076fc495e8b5df04d874f2911a838883a.png" alt="$ d $" />-dimensional (hyper)cube <img class="teximage" src="/files/tex/285c5204273d3b499eea40b8b9ea3d2a2f1be0f8.png" alt="$ Q_d $" /> is the graph whose vertices are all binary sequences of length <img class="teximage" src="/files/tex/aeba4a4076fc495e8b5df04d874f2911a838883a.png" alt="$ d $" />, and two of the sequences are adjacent in <img class="teximage" src="/files/tex/285c5204273d3b499eea40b8b9ea3d2a2f1be0f8.png" alt="$ Q_d $" /> if they differ in precisely one coordinate.</p> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; <img class="teximage" src="/files/tex/8a347f2f5bc9527051396b3f7efcdc793f5c87f0.png" alt="$ \displaystyle \lim \frac{cr(Q_d)}{4^d} = \frac{5}{32} $" /> </div> </tr></td> </table> </td> </tr> </table> Erdos, Paul Guy, Richard K. crossing number hypercube Graph Theory Topological Graph Theory Crossing numbers http://openproblemgarden.org/op/the_crossing_number_of_the_hypercube#comment Fri, 11 May 2007 08:55:03 +0200 Robert Samal 313 at http://openproblemgarden.org