For a finite graph $G$, we say a matrix $B\in \mathbb{R}^{n\times n}$ represents $G$ if $B$ belongs to this set: $$\mathscr{B}=\{ B=(b_{ij}) \mid B\textrm{ is positive semidefinite with trace at most 1 and } b_{ij}=0 \textrm{ if } i \textrm{ and } j \textrm{ are adjacent vertices of } G \textrm{ } (i\neq j) \}.$$ In the above set, considering only the elements of the upper triangle and ignoring those entries which correspond to $i$ and $j$ being adjacent, we have a $n(n+1)/2-|E|$-dimensional space which is full dimensional. Let the set of all points of this space be $\mathscr{A}$. Find an interior point $a_0$ and numbers $r,R<\infty, r>0$ such that the ball $S(a_0,r)$ is contained in $\mathscr{A}$ and $S(a_0,R)$ contains $\mathscr{A}$.

I see that the matrix $\frac{1}{2n}I$ corresponds to $a_0$ with $r=\frac{1}{2n^2}$ and this is an interior point of $\mathscr{A}$. But how do we find $R$? I'm not even sure that $\mathscr{A}$ is bounded.

(A set $S\in \mathbb{R}^n$ is full dimensional if it contains an $n$-dimensional ball. Alternatively, any element $z\in \mathbb{R}^n$ can be written as $z=x-y$ for some $x,y\in S$.)


Your Answer

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

Browse other questions tagged or ask your own question.