http://www.openproblemgarden.org/op/coloring_random_subgraphs Comments for "Coloring random subgraphs" en http://www.openproblemgarden.org/op/coloring_random_subgraphs#comment-6652 <p>I haven't worked through the details yet, but what if <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> is the union of <img class="teximage" src="/files/tex/3047d5de14f4534bc7c4d3e1d86c3fb292aea727.png" alt="$ K_n $" /> and a sufficiently huge bipartite graph <img class="teximage" src="/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png" alt="$ H $" />? Then <img class="teximage" src="/files/tex/ffbda66074e8e8a82d15bc9f2a32c59ce7ca4d80.png" alt="$ \chi(G) = n $" />, and by taking <img class="teximage" src="/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png" alt="$ H $" /> huge enough, you can get <img class="teximage" src="/files/tex/1b90136e328ae660c78437ea8dc532cd86a5dbee.png" alt="$ \mathbb{E}(\chi(G_{1/2})) $" /> as close to 2 as you like, forcing <img class="teximage" src="/files/tex/dccee841f3f498c2c58fa6ae1c1403c5a88c5b8d.png" alt="$ c $" /> as small as you like. </p> <p>EDIT: Whoo boy. Nevermind.</p> Thu, 04 Jun 2009 18:38:14 +0200 chrisrudy502 comment 6652 at http://www.openproblemgarden.org http://www.openproblemgarden.org/op/coloring_random_subgraphs <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/bukh_boris">Bukh</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/random_graphs">Probabilistic G.T.</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <p>If <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> is a graph and <img class="teximage" src="/files/tex/1d076f7332523eb59bd7deae19667f83f0a3b6e0.png" alt="$ p \in [0,1] $" />, we let <img class="teximage" src="/files/tex/9e4d593c7cf31e16440eb9935dac219a419a07ef.png" alt="$ G_p $" /> denote a subgraph of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> where each edge of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> appears in <img class="teximage" src="/files/tex/9e4d593c7cf31e16440eb9935dac219a419a07ef.png" alt="$ G_p $" /> with independently with probability <img class="teximage" src="/files/tex/928cd9d544fdea62f88a627aaee28c416c4366c0.png" alt="$ p $" />.</p> <div class="envtheorem"><b>Problem</b>&nbsp;&nbsp; Does there exist a constant <img class="teximage" src="/files/tex/dccee841f3f498c2c58fa6ae1c1403c5a88c5b8d.png" alt="$ c $" /> so that <img class="teximage" src="/files/tex/4b1ef3a1f1774128d4eb54d55c91dc24f252c1e2.png" alt="$ {\mathbb E}(\chi(G_{1/2})) &gt; c \frac{\chi(G)}{\log \chi(G)} $" />? </div> </tr></td> </table> </td> </tr> </table> Bukh, Boris coloring random graph Graph Theory Probabilistic Graph Theory http://www.openproblemgarden.org/op/coloring_random_subgraphs#comment Wed, 18 Jun 2008 07:56:41 +0200 mdevos 827 at http://www.openproblemgarden.org