Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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 question

share|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.