Extreme Laplacian eigenvalues - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T14:26:10Z http://mathoverflow.net/feeds/question/108993 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/108993/extreme-laplacian-eigenvalues Extreme Laplacian eigenvalues tobias 2012-10-06T12:32:25Z 2012-10-09T07:35:02Z <p>For each undirected (and unweighted) graph $G$ we define the Laplacian matrix by $L(G) = D(G)-A(G)$, where $A(G)$ should denote the adjacency matrix and $D(G)$ the diagonal matrix, where $D(G)_{ii}$ denotes the degree of the $i$-th vertex of $G$ (after some ordering of the vertex set). We denote the eigenvalues of $L(G)$ by $\lambda_0 = 0 \leq \lambda_1 \leq \ldots$</p> <p>If we consider the $n$-dimensional hypercube graph (see <a href="http://en.wikipedia.org/wiki/Hypercube_graph" rel="nofollow">http://en.wikipedia.org/wiki/Hypercube_graph</a> for more information), we obtain that the laplacian eigenvalues are $2i$ with multiplicity $\binom{n}{i}$ for $i=0,\ldots,n$. Hence, $\lambda_1 = 2$. The graph has $n\cdot 2^{n-1}$ edges.</p> <p>My question is now: Is there any method known to construct for increasing $n$ a graph $G$ with $2^n$ vertices and $n\cdot 2^{n-1}$ edges, where the $\lambda_1$ of $L(G)$ is bigger than 2 (the more the better)? And is there any estimate to these $\lambda_1$ then? Furthermore, it would interest me to consider such a kind graphes $G$, where $\lambda_1$ is still bigger than 2, but the graph itself looks quite similar to the $n$-dimensional hypercube graph, but this is only optional.</p> http://mathoverflow.net/questions/108993/extreme-laplacian-eigenvalues/109058#109058 Answer by Alain Valette for Extreme Laplacian eigenvalues Alain Valette 2012-10-07T13:29:04Z 2012-10-07T13:29:04Z <p>Let me turn the previous remarks into a tentative answer. Fix distinct primes $p,q$ and consider the Ramanujan graphs $X^{p,q}$ of Lubotzky-Phillips-Sarnak [A. Lubotzky, R. Phillips, P. Sarnak (1988). "Ramanujan graphs". Combinatorica 8 (3): 261–277]. These are $(p+1)$-regular graphs, which are Cayley graphs of $PSL_2(q)$ or $PGL_2(q)$ (depending on the Legendre symbol $(\frac{p}{q})$); at any rate $X^{p,q}$ has roughly $q^3$ vertices, and $\lambda_1(X^{p,q})\geq 2\sqrt{p}$ by the Ramanujan property.</p> <p>So if you take $q$ of the order of magnitude of $2^{(p+1)/3}$, you get a $(p+1)$-regular graph on approximately $2^{p+1}$ vertices, with $\lambda_1(X^{p,q})\geq 2\sqrt{p}$. However these graphs are very far from the hypercubes: they have large girth, they have large chromatic number (unless they are bipartite), etc...</p> http://mathoverflow.net/questions/108993/extreme-laplacian-eigenvalues/109119#109119 Answer by Aaron Meyerowitz for Extreme Laplacian eigenvalues Aaron Meyerowitz 2012-10-08T07:25:26Z 2012-10-09T07:35:02Z <p>Here is something which seems to work. Consider a <a href="http://en.wikipedia.org/wiki/Circulant_graph" rel="nofollow">circulant graph</a> with vertices $v_0,\cdots,v_{2^n-1}$ and $v_i$ adjacent to $v_{i\pm d}$ where $d$ ranges over a set $D$ of $\lceil\frac{n+1}{2}\rceil$ distances. For even $n,$ the distance $2^{n-1}$ is forbidden and the eigenvalues are $n-2\sum_D\cos(jd\omega)$ where $\omega=\frac{\pi }{2^{n-1}}$ and $j$ ranges from $1$ to $2^{n-1}.$ For $n$ odd, the distance $2^{n-1}$ is required and the eigenvalues are as before except that $\cos{j\pi}$ is subtracted only once.</p> <p>This gives a whole class of easily examined graphs. I would expect that picking distances which allow any vertex to get to any other in relatively few steps would lead to a large second eigenvalue. </p> <p>If I calculated correctly, then </p> <ul> <li>For $n=5$ we get $\lambda_1=2$ with $D=\lbrace 1,4,16 \rbrace.$ </li> <li>For $n=6$ we get $\lambda_1\approx 2.29637$ with $D=\lbrace 1,7,18 \rbrace$ </li> <li>For $n=7$ again $\lambda_1\approx 2.29637$ is optimal using $D=\lbrace 1,7,18,64 \rbrace.$ </li> <li>The case $n=8$ was taking too long (with a naive program) but the best value when $D=\lbrace 1,7,a,b \rbrace$ is $\lambda_1 \approx 2.550198$ attained by $D=\lbrace 1,7,18,99 \rbrace.$ </li> </ul>