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.

  • 1
    $\begingroup$ If your graph is $k$-regular, then $k-\lambda_1$ is the second-largest eigenvalue and, if you want $k-\lambda_1$ large, you are looking for something like an expander, where $\lambda_1$ is of order $2\sqrt{k-1}$. There is a large literature here, which I suspect will not be very helpful - the basic strategy to construct expanders is to take a sparse Cayley graph, but you want a Cayley graph for a group of order $2^n$, which is nilpotent. This means you will probably not be able to get anything like an expander, but you might do better than 2. $\endgroup$ – Chris Godsil Oct 6 '12 at 13:29
  • $\begingroup$ Do you insist on having exactly $2^n$ vertices and $n.2^{n-1}$ edges (which means average degree is exactly $n$)? Or is the order of magnitude good enough? $\endgroup$ – Alain Valette Oct 6 '12 at 15:14
  • $\begingroup$ Well, since I could perhaps modify a quite close graph in such a way that it fits my restrictions one might consider also somewhat relaxed restrictions. $\endgroup$ – tobias Oct 6 '12 at 16:40
  • $\begingroup$ Presumably a random graph with degree $n$ will have $\lambda_1$ approximately equal to $\sqrt{n}.$ I assume you want an explicit construction? $\endgroup$ – Igor Rivin Oct 6 '12 at 19:03

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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.