I want to use for some work of mine bounded-degree (balanced bipartite) expanders with "decent" spectral gap. They need not be Ramanujan graphs. I'm ok with a degree that's a constant factor (ideally smallish) larger than the minimum necessary for a given ratio $\lambda_1/\lambda_2$, where $\lambda_1$ and $\lambda_2$ are the two largest eigenvalues.

But, in order of importance:

  1. I must have strong control on their size; at the very least I need to be able to construct them with size equal to every power of $2$. "An infinite family" is not nearly good enough for me, even an "infinite linear family" is iffy.

  2. I must have some control on their degree; let's say there must be a (smallish) constant $c$ such that for every $d$, I must be able to grab family with degrees between $2^d$ and $2^{d+c}$, guaranteeing me a second eigenvalue no larger than $2^{(d+c)/2+1}$.

  3. They must admit a fully explicit construction, in "little" time, ideally linear or slightly superlinear. "Polynomial" is not nearly as good.

  4. Ideally, the constants involved must not be gargantuan, but this has much lower priority than 1,2 or 3.

  5. "Simple" would be icing on the cake...

None of the constructions of Ramanujan or "quasi-Ramanujan" graphs I've seen seem to satisfy 1 & 3, and most fail to satisfy 4; but maybe I've been just too hasty. Any pointer would be greatly appreciated!


Your Answer

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

Browse other questions tagged or ask your own question.