Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
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. –  Chris Godsil Oct 6 '12 at 13:29
    
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? –  Alain Valette Oct 6 '12 at 15:14
    
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. –  tobias Oct 6 '12 at 16:40
    
Presumably a random graph with degree $n$ will have $\lambda_1$ approximately equal to $\sqrt{n}.$ I assume you want an explicit construction? –  Igor Rivin Oct 6 '12 at 19:03
add comment

2 Answers

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.$
share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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