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?Related questionReverse Graph Spectra Problem?
Generating a random graph with constraints on spectrum
ds.algorithms;graph theory;randomness;spectral graph theory