4
$\begingroup$

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 ^_^

$\endgroup$
2
  • $\begingroup$ crossposted to cstheory.se $\endgroup$ – HallaSurvivor Nov 17 '20 at 4:44
  • $\begingroup$ It would be better to note the crossposting in your question than in a comment. $\endgroup$ – robjohn Nov 30 '20 at 17:43
1
$\begingroup$

Indeed, here is a way to construct (regular) graphs of size $O(n^{3/2})$ while controlling the (approximate) algebraic connectivity $a_c \in [0,2]$ with an error of order $1 \over n$.

The rough idea is to start with a graph $G$ with small connectivity $\mu$ and to generate a family of product of graph $(G[H_k])_k$ whose connectivities are going to be $k \mu$. Using this, we can have an approximation as good as we want, given that $\mu$ can be taken arbitrarily small.

It is known (see Biggs algebraic graph theory cited here, table 3.2) that: $$a_c(C_n) = 2(1-\cos({2\pi \over n}))$$

Hence we can start from a $2$-regular graph with an algebraic $a_c(G)$ as small as we want. Since $2(1-\cos({2\pi \over \ell})) \sim_0 {8\pi\over \ell^2}$, we even control the size of $G$ as a function of the precision, and we are going to use $C_{\sqrt{n}}$.

Now we are going to use lexicographic product of graphs

lexicographic product, from wikipedia

We have $(g,h) \sim_{G[H]} (g',h')$ if $g \sim_G g'$ or $g=g'$ and $h\sim_H h'$, hence the lexicographic product of regular graph is regular.

Moreover, the algebraic connectivity of the lexicographic product is well understood

Theorem 27.Let $F$ be a connected graph with vertex set $\{u_1, . . . , u_m\}$ and $H$ be any graph of order $n$. [...] $$a_c(F[H]) = min \{a_c(H) +\delta(F)n, a_c(F)n\}$$ where $\delta(F)$ denotes the minimum degree vertices in a graph $G$.

here $\delta(C_n)=2$ so $a_c(F[H]) =n a_c(C_{\sqrt{n}}) $ for reasonable choices of $H$. In order to get a (4-)regular graph, we are going to use the family $(H_k)_{k={2,...,2n}} = (C_k)_{k={2,...,2n}}$, which allow use to get the algebraic connectivities approximately $({8\pi k \over n})_{k={2,...,2n}}$ for the graphs $(G[H_k])_{k={2,...,2n}}=(C_{\sqrt{n}}[C_k])_{k={2,...,2n}}$.

$\endgroup$

Your Answer

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

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