MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


does the following inequality holds for every graph?


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.

share|cite|improve this question
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.

share|cite|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.