Number of matchings of even cycles

Question

By doing some calculations on the generating function of matching polynomials of cycles I made the following interesting observation:

• For all positive integers $n>1$ and $k <n $, the number of matchings of size $k $ in $C_{2n} $ is equal to the number of matchings of the same size in the disjoint union of two $C_n $'s.

As mentioned, I have only an algebraic proof of this elementary result. Does anyone have a more illuminating proof?

Answer 1

There is in fact a topological(?) proof of this statement and the following generalization, essentially due to Péter Csikvári (in "Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems", Section 4, Lemma 4.2).

We define a double cover (or "2-lift") $H$ of a graph $G$ as follows: consider $G$ as a topological space with CW structure, and $\pi:H\to G$ is a topological double cover with CW structure induced from $G$. Let $G\sqcup G$ denote the disconnected double cover of $G$. Let $m_k(G)$ denote the number of $k$-edge matchings in $G$.

Proposition. Let $G$ be a graph with no cycle of length smaller than $g$ (e.g. let $g$ be the girth of $G$) and let $H$ be a double cover of $G$. Then for any $k < g$, $$m_k(H) = m_k(G\sqcup G) .$$

Proof: Consider a $k$-matching $M\subset H$, and consider its image $\pi(M)$ in $G$. The image has vertices of valence at most 2, so $\pi(M)$ is a disjoint union of paths and cycles. But since $k < g$, there are no cycles. Observe that any path in $G$ lifts to a matching in $H$ in exactly two ways. Thus $m_k(H) = m_k(H')$ where $H$ and $H'$ are any double covers. Since $G\sqcup G$ is a double cover, the result follows.

---

Csikvári observed that when $G$ is bipartite, the same type of argument, now accounting for (even) cycles, implies that $$m_k(H) \leq m_k(G\sqcup G) $$ for any size matching $k$. This is used to prove tight lower bounds on the number of matchings in a bipartite, $d$-regular graph.

Answer 2

Here is a bijective proof.

Label the vertices of $C_{2n}$ as $1, 2, \dots, n, 1', 2', \dots, n'$ in clockwise order and let $M$ be a matching of size $k<n$ in $C_{2n}$. Since $M$ is not a perfect matching, there must exist $i$ such that both of the edges $(i, i+1)$ and $(i', (i+1)')$ are not in $M$ (note that if $i=n$, then $i+1=1'$ and $(i+1)'=1$). Choose $i$ minimum and replace the edges $(i,i+1)$ and $(i', (i+1)')$ by the edges $(i, (i+1)')$ and $(i', i+1)$. This creates two copies of $C_n$ where the numbers $1, \dots, n$ appear in each copy (although some are primed and some not). Rename all the vertices in the copy of $C_{n}$ containing $1'$ as primed vertices, and rename all the vertices in the copy of $C_{n}$ containing $1$ so that they are not primed. Note that this process is reversible, so this gives the required bijection.

This is joint work (possibly over beer) with Aurélien Ooms.