Question

hey,

does the following inequality holds for every graph?

$d(G)\geq\theta(G)$

while $\theta$ is the lovasz theta function and $d(G)$ is the minimum rank over all the matrices that represent the graph $G$.

thanks everybody.

Answer 1

If you mean minimum rank over matrices which "fit" the graph, as described by Haemers 1978, then the answer is no. Note: as mentioned on Wikipedia, there is a typo and Haemers meant that the matrix should be nonzero down the diagonal and zero in positions $(i,j)$ for which vertices are not adjacent. The minimum rank over matrices which fit the graph is denoted $R(G)$. For most graphs, $R(G) \ge \theta(G)$, however the Haemers paper gives examples where the opposite is true.