http://www.openproblemgarden.org/op/signing_a_graph_to_have_small_magnitude_eigenvalues Comments for "Signing a graph to have small magnitude eigenvalues" en http://www.openproblemgarden.org/op/signing_a_graph_to_have_small_magnitude_eigenvalues <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/bilu_yonatan">Bilu</a>; <a href="/category/linial">Linial</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; If <img class="teximage" src="/files/tex/7a8d9782350e8eb5a84c149576d83160492cbdd3.png" alt="$ A $" /> is the adjacency matrix of a <img class="teximage" src="/files/tex/aeba4a4076fc495e8b5df04d874f2911a838883a.png" alt="$ d $" />-regular graph, then there is a symmetric signing of <img class="teximage" src="/files/tex/7a8d9782350e8eb5a84c149576d83160492cbdd3.png" alt="$ A $" /> (i.e. replace some <img class="teximage" src="/files/tex/155fca3c17d66548c323f203be786f9387842fe4.png" alt="$ +1 $" /> entries by <img class="teximage" src="/files/tex/26833acbe5abb13c40595cebdee81f595c59a397.png" alt="$ -1 $" />) so that the resulting matrix has all eigenvalues of magnitude at most <img class="teximage" src="/files/tex/40581c05b66d632e7bdb2bcb852e63443663853a.png" alt="$ 2 \sqrt{d-1} $" />. </div> </tr></td> </table> </td> </tr> </table> Bilu, Yonatan Linial, Nathan eigenvalue expander Ramanujan graph signed graph signing Graph Theory http://www.openproblemgarden.org/op/signing_a_graph_to_have_small_magnitude_eigenvalues#comment Sun, 24 Mar 2013 15:33:19 +0100 mdevos 48264 at http://www.openproblemgarden.org