# Generating a random graph with constraints on spectrum

Consider two sequences $$u_1 \geq u_2 \geq ... \geq u_n$$ and $$l_1 \geq l_2 \geq ... \geq l_n$$ with $$u_i \geq l_i$$ for every $$i$$. Let $$\mathcal{G}(l_{1:n},u_{1:n})$$ be all undirected unweighted simple graphs on $$n$$ vertices that have their spectrum lower-bounded by $$l_{1:n}$$ and upper-bounded by $$u_{1:n}$$. In other words, let $$G$$ be a graph on $$n$$ vertices, and $$\lambda_1 \geq \lambda_2 \geq ... \geq \lambda_n$$ the eigenvalues of $$G$$'s adjacency matrix; if $$l_i \leq \lambda_i \leq u_i$$ for all $$i$$ then $$G \in \mathcal{G}(l_{1:n},u_{1:n})$$.

Is there an efficient procedure to sample a graph uniformly at random from $$\mathcal{G}(l_{1:n},u_{1:n})$$? If not, what restrictions do we need to place on $$l_{1:n}$$, $$u_{1:n}$$, or elsewhere to have such a procedure? What if we just need the distribution over $$\mathcal{G}(l_{1:n},u_{1:n})$$ to be approximately uniform?

In the application I am considering, I really only care about the first few eigenvalues (biggest 2 or 3). If we constain only $$l_i \leq \lambda_i \leq u_i$$ for all $$i \in \{1,2\}$$ or $$i \in \{1,2,3\}$$ (instead of all $$i$$ as before) then is there a good sampling algorithm?

If no good sampling algorithm is known even in the restricted case then what do people usually do in practice?