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.
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. 


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. 

