http://openproblemgarden.org/op/ramsey_properties_of_cayley_graphs Comments for "Ramsey properties of Cayley graphs" en http://openproblemgarden.org/op/ramsey_properties_of_cayley_graphs <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/alon">Alon</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/algebraical_graph_theory">Algebraic G.T.</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; There exists a fixed constant <img class="teximage" src="/files/tex/dccee841f3f498c2c58fa6ae1c1403c5a88c5b8d.png" alt="$ c $" /> so that every abelian group <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> has a subset <img class="teximage" src="/files/tex/1443dce39cbce9606ca2c26bfb4ffbcf28ddb2c9.png" alt="$ S \subseteq G $" /> with <img class="teximage" src="/files/tex/c931921f156211c8e73ee3e57353f799f2676a34.png" alt="$ -S = S $" /> so that the <a href="http://en.wikipedia.org/wiki/cayley graph">Cayley graph</a> <img class="teximage" src="/files/tex/f0cecf17b88dfdb3db14ed2c21bce70a47d051cd.png" alt="$ {\mathit Cayley}(G,S) $" /> has no clique or independent set of size <img class="teximage" src="/files/tex/e224dcfe2b20fdd16ed3f4a07612dc76b28666fe.png" alt="$ &gt; c \log |G| $" />. </div> </tr></td> </table> </td> </tr> </table> Alon, Noga Cayley graph Ramsey number Graph Theory Algebraic Graph Theory http://openproblemgarden.org/op/ramsey_properties_of_cayley_graphs#comment Sun, 10 Jun 2007 08:07:59 +0200 mdevos 372 at http://openproblemgarden.org