A New [Combinatorial] Proof of the Commutativity of Matching Polynomials for Cycles

Abstract

We prove some functional equations involving the (classical) matching polynomials of path and cycle graphs and the $d$-matching polynomial of a cycle graph. A matching in a (finite) graph $G$ is a subset of edges no two of which share a vertex, and the matching polynomial of $G$ is a generating function encoding the numbers of matchings in $G$ of each size. The $d$-matching polynomial is a weighted average of matching polynomials of degree-$d$ covers, and was introduced in a paper of Hall, Puder, and Sawin. Let ${\mathcal{C}}_n$ and ${\mathcal{P}}_n$ denote the respective matching polynomials of the cycle and path graphs on $n$ vertices, and let ${\mathcal{C}}_{n,d}$ denote the $d$-matching polynomial of the cycle $C_n$. We give a purely combinatorial proof that ${\mathcal{C}}_k({\mathcal{C}}_n(x))={\mathcal{C}}_{kn}(x)$ en route to proving a conjecture made by Hall: that ${\mathcal{C}}_{n,d}(x)={\mathcal{P}}_d({\mathcal{C}}_n(x))$.

17 pages, 7 figures