Extreme Laplacian eigenvalues

Question

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$

If we consider the $n$-dimensional hypercube graph (see http://en.wikipedia.org/wiki/Hypercube_graph 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.

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.

Answer 1

Here is something which seems to work. Consider a circulant graph 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.

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.

If I calculated correctly, then

• For $n=5$ we get $\lambda_1=2 $ with $D=\lbrace 1,4,16 \rbrace.$
• For $n=6$ we get $\lambda_1\approx 2.29637 $ with $D=\lbrace 1,7,18 \rbrace$
• For $n=7$ again $\lambda_1\approx 2.29637 $ is optimal using $D=\lbrace 1,7,18,64 \rbrace.$
• 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.$

Answer 2

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.

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...