http://openproblemgarden.org/op/the_sum_of_the_two_largest_eigenvalues Comments for "The sum of the two largest eigenvalues" en http://openproblemgarden.org/op/the_sum_of_the_two_largest_eigenvalues#comment-5102 <p>The paper shows that the sum of the first two eigenvalues exceeds 1.125n - 25, so exceeds n when n is sufficiently large. Thus Nikiforov has given a negative solution to the problem. (Note: I have not checked the claims of the paper thoroughly.)</p> Tue, 13 Jan 2009 16:39:51 +0100 Michael Slone comment 5102 at http://openproblemgarden.org http://openproblemgarden.org/op/the_sum_of_the_two_largest_eigenvalues#comment-948 <p>Yes. Nikiforov's inequality says that for all n >= 21 the maximum of the sum of the two largest eigenvalues of a graph on n vertices is at least f(n):=n(29+sqrt(329))/42-25. Notice that for n >= 204, f(n)-n is positive. Thus, for all n >= 204 there is a graph with n vertices and with the sum of the two largest eigenvalues greater than n. </p> <p>Take a look at http://garyedavis.wordpress.com/ for an example and 3D picture of a graph on 40 vertices, with 770 edges for which the sum of the two largest eigenvalues is > 40.</p> <p>I don't know if anyone knows the least n for which there is a graph with n vetices such that the sum of the two largest eigenvalues is greater than n.</p> <p>Regards,</p> <p>Gary Davis</p> Sun, 29 Jun 2008 22:49:54 +0200 Anonymous comment 948 at http://openproblemgarden.org http://openproblemgarden.org/op/the_sum_of_the_two_largest_eigenvalues#comment-552 <p>I'm confused how the paper's result (which you have posted) solves this question. I didn't read the paper, but the abstract only gave a looser bound that the sum of the first two eigenvalues is <= 2/sqrt(3) * n (and not just n).</p> Wed, 18 Jun 2008 23:14:11 +0200 Anonymous comment 552 at http://openproblemgarden.org http://openproblemgarden.org/op/the_sum_of_the_two_largest_eigenvalues#comment-182 <p>About 5 months ago, I was shown a counterexample to this conjecture by Bojan Mohar (I believe in joint work with two of his grad. students - Javad Ebrahimi and Azhvan Sheikh). However, thanks to Gordon Royle, I have just learned that this problem was resolved earlier by Vladimir Nikiforov. See <a href="http://www.math.technion.ac.il/iic/ela/ela-articles/articles/vol15_pp329-336.pdf">Linear combinations of graph eigenvalues</a>. </p> Thu, 06 Sep 2007 20:49:26 +0200 mdevos comment 182 at http://openproblemgarden.org http://openproblemgarden.org/op/the_sum_of_the_two_largest_eigenvalues <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/gernert_dieter">Gernert</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>Problem</b>&nbsp;&nbsp; Let <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> be a graph on <img class="teximage" src="/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png" alt="$ n $" /> vertices and let <img class="teximage" src="/files/tex/4dab458778057be2d191e80cde57ee36191958e9.png" alt="$ \lambda_1 \ge \lambda_2 \ge \ldots \ge \lambda_n $" /> be the eigenvalues of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" />. Is <img class="teximage" src="/files/tex/a383bcff06b594eb75570de2cd8813be94854126.png" alt="$ \lambda_1 + \lambda_2 \le n $" />? </div> </tr></td> </table> </td> </tr> </table> Gernert, Dieter eigenvalues spectrum Graph Theory Algebraic Graph Theory http://openproblemgarden.org/op/the_sum_of_the_two_largest_eigenvalues#comment Wed, 06 Jun 2007 19:46:30 +0200 mdevos 353 at http://openproblemgarden.org