1
$\begingroup$

Can we infer from the fact that the number of independent sets in product of $5$-cycle two times is $5$ and in product of $5$-cycle four times is $25$, that the capacity of pentagon is $\sqrt{5}$? That is does $\alpha(C_5 \boxtimes C_5)=5$ and $\alpha(C_5 \boxtimes C_5\boxtimes C_5 \boxtimes C_5)=25$ imply $\theta(C_5)=\sqrt{5}$? Why? Or why not then?

Here $C_5$ is pengtagon, $\alpha(G)$ is independence number of graph $G$, $\boxtimes$ is strong product and $\theta(G)$ is Shannon capacity of graph $G$.

$\endgroup$
1
$\begingroup$

From the givens you can only deduce that the Shannon capacity is at least $\sqrt{5}$. For example, it could be that $\alpha(C_5^8)^{1/8} > \sqrt{5}$, which doesn't contradict your data.

As an aside, the Shannon capacity is usually denoted by $\Theta$, whereas $\theta$ is the Lovász function, which is an upper bound on the Shannon capacity. From the givens you can only deduce that $\theta(C_5) \geq \sqrt{5}$.

$\endgroup$
  • $\begingroup$ So you are saying even though $\alpha(C_n^{m_1m_2})=\alpha(C_n^{m_1})^{m_2}$ seems to stabilize, the higher powers may satisfy $\alpha(C_n^{m_1m_2m_3})>\alpha(C_n^{m_1})^{m_2m_3}$? $\endgroup$ – Turbo Nov 9 '14 at 6:18
  • $\begingroup$ I can see the lower bound easily. However is there an evidence or a proof that the bound is strict even after some lower powers stabilize in independence number (stabilize in the context of the equality in the question)? $\endgroup$ – Turbo Nov 9 '14 at 15:37
  • $\begingroup$ We know that the capacity of the pentagon is $\sqrt{5}$, since we know that $\theta(C_5) = \sqrt{5}$ (here $\theta$ is the Lovász function). Regarding the behavior of powers, I recall someone mentioning that it could stabilize and then grow at an arbitrary power, but that is a separate question you might want to ask. $\endgroup$ – Yuval Filmus Nov 9 '14 at 16:30

Your Answer

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

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