A maximum independent set is a largest independent set for a given graph $G$ and its size is denoted $\alpha(G)$. And the Lovász number of $G$ is denoted $\vartheta(G)$. $\vartheta(G)\geq \alpha(G)$ by definition, then the question is what will the $$\max\limits_G \frac{\vartheta(G)}{\alpha(G)}$$ be? Any known results about this topic will be welcome! One can give examples to show how big could the ratio $\vartheta(G)/\alpha(G)$ be or counter-examples to show the ratio will go to infinity. Any help or suggestions will be appreciated!

P.S. here is a related question:Cliques, Paley graphs and quadratic residues.


It is infinite, in fact much stronger versions are also true, see e.g., Theorem 1 here: http://arxiv.org/abs/cs/0608021 (Shannon capacity is between $\alpha$ and $\vartheta$.)


I don't have a proof, but numerical evidence seems to indicate the ratio is unbounded. Consider the Paley graphs $P(q)$. Then it is known that $\vartheta(P(q))=\sqrt{q}$. On the other hand, calculations (more here) appear to show that $\alpha(P(q))$ is roughly $2\log(q)$, and of course $\frac{\sqrt{q}}{2\log(q)}\rightarrow\infty$ as $q\rightarrow\infty.$

Added later: I checked a little further and it should be noted that when $q=k^2$, where $k$ is an odd prime power, the independence number is known to be exactly $\sqrt{q}$, so I think the calculations I linked to do not include these cases. On the other hand, if $q$ is not of that form, then an old paper of Stephen D. Cohen ("Clique numbers of Paley graphs", Quaestiones mathematicae, 11, no. 2 (1988)) apparently shows that the expected value of $\alpha(P(q))$ is $\log_2(q)+\frac{3}{2}.$ Unfortunately, I don't have access to that paper, so I can't investigate this further. Anyway, sorry for the haphazard answer.

  • $\begingroup$ Thanks! Your answer is very helpful! I also considered Payley graphs, but it is not adequate to say the upper bound is infinity because the numerical result shows the maximum is $5.4$ for $q<9973$. Is there some other pattern of graphs whose $ϑ(G),α(G)$ are all known? Thanks again! $\endgroup$ – Eden Harder Oct 27 '13 at 13:16
  • $\begingroup$ Yes I meant it just looked like it'll be unbounded from that data. I have no idea if it actually is. I am not up to date on the recent literature so I don't know of any other pattern besides the ones listed in those links, sorry! I am sure there are others on MO much more knowledgeable about this stuff. $\endgroup$ – Casteels Oct 27 '13 at 13:42
  • $\begingroup$ Thanks so much! Here is a similar question shows $log_2(q)+3/2$ will not be the right size. $\endgroup$ – Eden Harder Oct 28 '13 at 14:20
  • $\begingroup$ Ah yes. Well, as I said, there are people around here who know much more about this stuff than me! Good luck with your investigations! $\endgroup$ – Casteels Oct 28 '13 at 14:34
  • $\begingroup$ Thanks so much Casteels! You're so kindly focus on this question. $\endgroup$ – Eden Harder Oct 29 '13 at 0:25

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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