Let $C_m$ be the cycle with $m$ vertices, defined so that $C_1$ has a self-loop on its unique vertex. Let $p_m$ be the generating function enumerating the number of ways to choose $k$ vertices in $C_m$ so that no two are adjacent. Thus the coefficient of $z^k$ in $p_m(z)$ is the number of independent sets in $C_m$ of size $k$.

For instance, $p_1(z) = 1$, $p_2(z) = 1+2z$, $p_3(z) = 1+3z$, $p_4(z) = 1+4z + 2z^2$, $p_5(z) = 1 + 5z+5z^2$ and $p_6(z) = 1 + 6z + 9z^2 + 2z^3$. Set $p_0 = 2$.

It is not hard to show by algebraic arguments (related to the theory of Chebyshev polynomials) that if $\ell, m \in \mathbb{N}_0$ with $\ell \ge m$ then

$$p_\ell p_m = p_{\ell+m} + (-1)^m z^{m} p_{\ell-m}.$$

In particular, $p_m^2 = p_{2m} + 2(-1)^m z^{m}$, and so if $k < m$ then the coefficients of $z^k$ in $p_m^2$ and $p_{2m}$ are equal. I would like a bijective proof of this, or ideally, of the more general identity above.

Is there a bijective proof that if $k < m$ then the number of independent sets of size $k$ in the disjoint union $C_m \sqcup C_m$ is equal to the number of independent sets of size $k$ in $C_{2m}$?

  • $\begingroup$ But how do you prove that identity? A priori the $p_m$ are just some polynomials, which of their properties do you use in the proof? $\endgroup$ – მამუკა ჯიბლაძე Jul 6 at 19:27
  • 1
    $\begingroup$ I think this is in I. Gutman, F. Harary, Generalizations of the matching polynomial, Utilitas Mathematica 24 (1983) 97-106. $\endgroup$ – Martin Rubey Jul 6 at 19:50
  • 3
    $\begingroup$ The result also appears as Problem 11898, American Math. Monthly 123 (March 2016), but the published solution (in a later issue that I don't have a reference for) is not bijective. $\endgroup$ – Richard Stanley Jul 6 at 19:59
  • 1
    $\begingroup$ The solution appears in The American Math. Monthly 125 (January 2018). $\endgroup$ – RobPratt Jul 6 at 21:10
  • 1
    $\begingroup$ Here is a link to R. Tauraso's solution: mat.uniroma2.it/~tauraso/AMM/AMM11898.pdf. Incidentally Richard is very modestly not mentioning that he proposed the problem. $\endgroup$ – Mark Wildon Jul 8 at 11:22

It seems that I’ve seen this question here before, but I am not sure whether it had a bijective answer. Anyway, here you are.

Enumerate the vertices in two copies of $C_m$ as $1,2,\dots,m$ and $1’,2’,\dots,m’$, respectively. Take any independent set of size $k<m$ in the union of these cycles (regard it as marking some vertices). Choose the smallest $i$ such that both $i$ and $i’$ are not in the set. Arranging the vertices in the order $$ 1,2,\dots,i,(i+1)’,(i+2)’,\dots, m’, 1’, \dots,i’,i+1,i+2,\dots,m $$ you get a $C_{2m}$ with an independent set being marked.

The inverse map is to take $k$ marked vertices in $C_{2m}$, choose the smallest $i$ such that both $i$ and $i+m$ are not marked, cut $C_{2m}$ after them, and glue into two copies of $C_m$.

The same argument works for an arbitrary number of copies of $C_m$ (and still $k<m$).

| cite | improve this answer | |

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.