Let $\alpha(C_{n}^{\boxtimes k})$ be independence number of $k$-fold strong product of an $n$-vertex cycle graph $C_{n}$.

$\forall n > 6$, is $\alpha(C_{n}^{\boxtimes (k+r)})^{\frac{1}{k+r}} \geq \alpha(C_{n}^{\boxtimes k})^{\frac{1}{k}}$ for infinitely many positive integer pairs $(k,r)$?

  • $\begingroup$ Doesn't it follows directly from super-multiplicativity of $\alpha(C_n^k)^{1/k}$? Just take any $k$ and $r=1$. $\endgroup$ – Igor Shinkar Aug 11 '13 at 14:17
  • $\begingroup$ Sorry, i think my previous comment is incorrect. I meant that the sequence $(\alpha(G^k))_{k \geq 1}$ is super-multiplicative. $\endgroup$ – Igor Shinkar Aug 11 '13 at 15:23
  • 1
    $\begingroup$ So $\alpha(G^{2k}) \geq \alpha(G^{k})\alpha(G^{k}) \implies \alpha(G^{2k})^{\frac{1}{2k}} \geq \alpha(G^{k})^\frac{1}{k}$ and we can take $r=k$? Is there a reference for supermultiplicativity? $\endgroup$ – 1.. Aug 11 '13 at 15:35
  • $\begingroup$ Right, your example is much easier. The super-multiplicativity is just by taking product of the maximal independent sets on the RHS. $\endgroup$ – Igor Shinkar Aug 11 '13 at 15:40

It is a standard fact that $\lim_{k \to \infty} \sqrt[k]{\alpha(G^k)}=\sup_{k \to \infty} \sqrt[k]{\alpha(G^k)}$ for every graph $G$. (See the proof below.) Denoting $b_k := \sqrt[k]{\alpha(G^k)}$, this implies that the tail of the sequence $(b_k)_{k \geq 1}$ cannot be monotone decreasing, and hence there are infinitely many $k$'s for which $b_{k+1} \geq b_k$, as required.

In order to prove that $\lim_{k \to \infty} \sqrt[k]{\alpha(G^k)}=\sup_{k \to \infty} \sqrt[k]{\alpha(G^k)}$ note that the sequence $(\alpha(G^k))_{k \geq 1}$ is super multiplicative, i.e., $\alpha(G^{k+\ell}) \geq \alpha(G^k) \alpha(G^\ell)$ for all $k,\ell \geq 1$. Indeed, if $I$ is an independent set in $G^k$, and $J$ is an independent set in $G^\ell$, then $I \times J$ is an independent set in $G^{k+\ell}$. Therefore, by (the multiplicative version of) Fekete's lemma it follows that $\lim_{k \to \infty} \sqrt[k]{\alpha(G^k)}=\sup_{k \to \infty} \sqrt[k]{\alpha(G^k)}$.


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.