2
$\begingroup$

This is crossposted from math stackexchange. This is my first time posting here, so let me know if I'm doing something wrong.


I would like to experiment with various spectral properties of graphs, but in order to do so in a controlled way, I need to be able to find graphs with specified spectral properties. Unfortunately, I'm struggling to find literature on the topic, and I'm beginning to think it might be Hard to figure out myself.

More concretely, say I give you a value $\lambda \in [0,2]$. Can you find a $d$-regular graph on $n \gg 1$ vertices whose (normalized) Laplacian has its first nonzero eigenvalue $\approx \lambda$?

Ideally, we could fix $d$ in advance and only vary $n$, but I'm open to solutions which allow $d$ to vary.

Now, obviously we can't relax the notion of $\approx \lambda$. Since $\lambda$ must be a root of the (degree $n$) characteristic polynomial of the laplacian it cannot be entirely arbitrary. Moreover, if we want to keep $n$ from getting "too big", approximation is necessary even when $\lambda$ is algebraic.

I also suspect this problem is Hard. Particularly if we want a deterministic algorithm (this is another reason to allow some wiggle room with $\lambda$). If we had a good handle on building graphs with given spectral properties, then we would be able to make good expanders using similar technology. Since that problem is currently quite hard, I suspect this one is too. My only hope is that the smallest eigenvalue may be easier to control than the largest one (which is what we would have to control to build an expander).

Are there any results for building graphs with a predetermined algebraic connectivity $\lambda$?

Thanks in advance ^_^


I see on this site there's a similar question here that I didn't find while googling. Seeing as that question is quite old, I think I'll ask this one anyways to see if there's any new results. Plus, I'm primarily interested in the (slightly easier?) problem of controlling only one eigenvalue.

$\endgroup$
  • $\begingroup$ This SE site explicitely disallows cross-posting. $\endgroup$ – Jan Johannsen Nov 17 '20 at 13:42

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.