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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.