show/hide this revision's text 3 added 213 characters in body

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

  • For $n=5$ we get $\lambda_1\approx 2.17157 \lambda_1=2 $ with $D=\lbrace 1,7,16 1,4,16 \rbrace.$ And for
  • For $n=6$ we get $\lambda_1\approx 2.29637 $ with $D=\lbrace 1,7,18 \rbrace$ and also
  • 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,9,30 1,7,a,b \rbrace$ (which is an isomorphic graph.)$\lambda_1 \approx 2.550198$ attained by $D=\lbrace 1,7,18,99 \rbrace.$
show/hide this revision's text 2 edited body

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=4$ n=5$ we get $\lambda_1\approx 2.17157 $ with $D=\lbrace 1,7,16 \rbrace.$ And for $n=5$ n=6$ we get $\lambda_1\approx 2.29637 $ with $D=\lbrace 1,7,18 \rbrace$ and also with $D=\lbrace 1,9,30 \rbrace$ (which is an isomorphic graph.)
show/hide this revision's text 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=4$ we get $\lambda_1\approx 2.17157 $ with $D=\lbrace 1,7,16 \rbrace.$ And for $n=5$ we get $\lambda_1\approx 2.29637 $ with $D=\lbrace 1,7,18 \rbrace$ and also with $D=\lbrace 1,9,30 \rbrace$ (which is an isomorphic graph.)