6
$\begingroup$

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.

$\endgroup$

2 Answers 2

6
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
5
  • $\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$ Oct 27, 2013 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, 2013 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$ Oct 28, 2013 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, 2013 at 14:34
  • $\begingroup$ Thanks so much Casteels! You're so kindly focus on this question. $\endgroup$ Oct 29, 2013 at 0:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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