A ${\displaystyle d}$-regular graph $G$ is a Ramanujan graph if $${\displaystyle \lambda_1 (G)\leq 2{\sqrt {d-1}}}.$$
I'm looking for a (bi-)cubic graph that is highly non ramanujan, i.e. $$ 2{\sqrt 2} < \lambda_1 (G) < 3.$$
Is anyone aware of a goog example? Largest $\lambda_1$ will be accepted as answer...
Pick your favorite connected $n$-vertex bicubic graph $G$. Now take two copies of $G$ and join them as follows: replace an edge $ab$ in one copy and and its twin $a'b'$ in the other copy with edges $ab'$ and $a'b$. This graph $H$ is "highly non-Ramanujan".
How do we find the largest eigenvalue below $3$? Well, $H$ has an eigenvalue of $3$ with multiplicity $1$ (corresponding to the all-$1$'s vector) and an eigenvalue of $-3$ with multiplicity $1$ (corresponding to the vector which is $+1$ on one side of the bipartition, and $-1$ on the other). The eigenvalue we want (and its eigenvector) is found by maximizing $$\frac{\mathbf x^{\mathsf T}\!A\mathbf x}{\mathbf x^{\mathsf T}\mathbf x}$$ (where $A$ is the adjacency matrix) over all vectors orthogonal to both of the eigenvectors we know.
We won't find the actual maximum, but we can get pretty close if we let $\mathbf x$ be the vector which is $+1$ on one copy of $G$, and $-1$ on the other. For this $\mathbf x$, the product $A\mathbf x$ agrees with $3\mathbf x$ at most vertices except at $a, b, a', b'$, where it is $\pm 1$ instead of $\pm 3$. Therefore we have $$\frac{\mathbf x^{\mathsf T}\!A\mathbf x}{\mathbf x^{\mathsf T}\mathbf x} = \frac{3n-4}{n} = 3 - \frac 4n.$$ The actual eigenvalue we want is somewhere between $3 - \frac 4n$ and $3$.
Thus, we get a $2n$-vertex graph with spectral gap less than $\frac 4n$.