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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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$.)

Improve this answer
$\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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .