http://openproblemgarden.org/op/the_crossing_number_of_the_complete_graph Comments for "The Crossing Number of the Complete Graph" en http://openproblemgarden.org/op/the_crossing_number_of_the_complete_graph#comment-953 <p>The same article below, that proves that <img class="teximage" src="/files/tex/8a78c11c4d6809f9ee34be2648385eea6f80f08f.png" alt="$ cr(K_{11})=100 $" /> and <img class="teximage" src="/files/tex/374f4df865344f18977ac355418678c7852c75a6.png" alt="$ cr(K_{12})=150 $" />, states that <img class="teximage" src="/files/tex/6721eea3f568b4cdb45a4d53f1f08bffef20c0e6.png" alt="$ 0.8594 \cdot Z(n)\leq cr(K_n) \leq Z(n) $" />.</p> Mon, 28 Jul 2008 15:32:18 +0200 Anonymous comment 953 at http://openproblemgarden.org http://openproblemgarden.org/op/the_crossing_number_of_the_complete_graph#comment-952 <p>It has been shown that <img class="teximage" src="/files/tex/668eb77bbd55aaaa30bfcc7fd1e9c456d06c0b5c.png" alt="$ \lim_{n\rightarrow\infty}\frac{cr(K_n)}{Z(n)}\geq 0.83 $" />, where <img class="teximage" src="/files/tex/ef3462afd4cd10cbc2f8b443bd89dbc536d11eab.png" alt="$ Z(n) $" /> is the conjectured value. For the proof, see de Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, R. B.; Salazar, G. Improved bounds for the crossing numbers of <img class="teximage" src="/files/tex/4b880f07355bcb48bef939b128497c0e38a8cfdd.png" alt="$ K\sb {m,n} $" /> and <img class="teximage" src="/files/tex/f9261bfdc372cf5807995f8bb7471f3d3a94c0a8.png" alt="$ K\sb n $" />. (2007).</p> Mon, 28 Jul 2008 09:22:57 +0200 Anonymous comment 952 at http://openproblemgarden.org http://openproblemgarden.org/op/the_crossing_number_of_the_complete_graph#comment-31 <p>The conjecture was recently verified for n=11 and 12 (<a href="http://dx.doi.org/10.1002/jgt.20249">The Crossing Number of <img class="teximage" src="/files/tex/b7e1370c91827e3dc1157baf20b0c429d64e0423.png" alt="$ K_{11} $" /> Is 100</a> by Shengjun Pan and R. Bruce Richter).</p> Tue, 10 Jul 2007 01:19:06 +0200 Robert Samal comment 31 at http://openproblemgarden.org http://openproblemgarden.org/op/the_crossing_number_of_the_complete_graph <table cellspacing="10"> <tr> <td> Author(s): <a href="/kpz_equation_central_limit_theorem"></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> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; <img class="teximage" src="/files/tex/ebb1eaf4332defb7fcc42f4cd3f4fcfc7a0138e7.png" alt="$ \displaystyle cr(K_n) = \frac 14 \floor{\frac n2} \floor{\frac{n-1}2} \floor{\frac{n-2}2} \floor{\frac{n-3}2} $" /> </div> </tr></td> </table> </td> </tr> </table> complete graph crossing number Graph Theory Topological Graph Theory Crossing numbers http://openproblemgarden.org/op/the_crossing_number_of_the_complete_graph#comment Fri, 11 May 2007 06:47:58 +0200 Robert Samal 307 at http://openproblemgarden.org