# What is the maximum of the ratio $\vartheta(G)/\alpha(G)$?

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.

-
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! –  Eden Harder Oct 27 '13 at 13:16
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. –  Casteels Oct 27 '13 at 13:42
Thanks so much! Here is a similar question shows $log_2(q)+3/2$ will not be the right size. –  Eden Harder Oct 28 '13 at 14:20
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! –  Casteels Oct 28 '13 at 14:34
Thanks so much Casteels! You're so kindly focus on this question. –  Eden Harder Oct 29 '13 at 0:25