Lovasz Theta Function provides short proof for the question, "is the Shannon Capacity of a graph($\Theta(G)$) greater than $r\in\Bbb R$?" if the answer is NO when $r$ is above a certain value (this value is $\vartheta(G)$). Assuming the Shannon capacity problem is non-computable, can one expect to have a different computable function that can lower the lower limit on $r$ (assume that function takes values of $\vartheta(G)$ wherever it is tight)?

  • $\begingroup$ We have a proof that the Lovasz theta function is not tight for some graph $G$. Consider a function which equals the Lovasz theta function for all graphs except $G$, but differs from the Lovasz theta function $G$. $\endgroup$ – Peter Shor Dec 9 '13 at 13:12
  • $\begingroup$ $\vartheta(G)$ is not tight for all $G$ is accommodated in the question. If one considers $\vartheta(G)$ as a coNP certificate, is there a certificate that is short and computable and give tighter than $\vartheta(G)$ for graphs for which $\vartheta(G)$ is not tight? This is the question I intended to ask in here. The computable function should take $\vartheta(H)$ values for graphs $H$ that are known to be tight for $\vartheta(H)$(like pentagon) and for other graphs produce proven tighter result? $\endgroup$ – T.... Dec 9 '13 at 13:55
  • 1
    $\begingroup$ So you want a certificate that does better than ϑ(G) for all graphs where ϑ(G) is not tight? That would give an algorithm that decides whether ϑ(G) is tight for a given graph, which I am pretty sure is a problem not known to be in P. $\endgroup$ – Peter Shor Dec 9 '13 at 13:59
  • $\begingroup$ Sure but is such a function computable for all graphs? $\endgroup$ – T.... Dec 9 '13 at 14:03
  • $\begingroup$ I don't understand your question now. If there is a different method than the Lovasz theta function of getting a bound on the Shannon capacity, then just take the minimum of the theta function and the other method. If the other method is computable, the minimum is a computable function. $\endgroup$ – Peter Shor Dec 9 '13 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.