10
$\begingroup$

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}$?

$\endgroup$
7
  • $\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, 2020 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$ Jul 6, 2020 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$ Jul 6, 2020 at 19:59
  • 1
    $\begingroup$ The solution appears in The American Math. Monthly 125 (January 2018). $\endgroup$
    – RobPratt
    Jul 6, 2020 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$ Jul 8, 2020 at 11:22

1 Answer 1

7
$\begingroup$

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$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.