# minimum rank - lovasz function inequality

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.

-
Can you clarify what you mean by a matrix "representing" the graph. Lovasz discusses a certain kind of matrix representation of a graph in his paper on the subject; is that the one you mean? –  Dimitrije Kostic Nov 13 '11 at 18:59
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.