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?

  • $\begingroup$ Here is an idea: consider the 8 edge 8 vertex graph G which is C_4 with four legs. Matchings in G which "avoid the square" or "use two sides" or "use just three vertices" of the square allow for natural bijective mappings between your two classes of matchings. The remaining case is one square side and the other two vertices. You might show that there are an equal number of problematic cases in both classes. Gerhard "You May Use Cyclical Reasoning" Paseman, 2017.10.11. $\endgroup$ – Gerhard Paseman Oct 11 '17 at 18:01
  • $\begingroup$ Even better: take the union of two paths of length 3. There are two orientations, horizontal and vertical, and (at least) four maps which preserve two coloring of the degree one vertices. For any matching which induces a coloring of a horizontal (C2n) orientation, pick a such a mapping to turn it into a vertical (2Cn) orientation. Gerhard "This Seems Illuminating To Me" Paseman, 2017.10.11. $\endgroup$ – Gerhard Paseman Oct 11 '17 at 18:14

There is in fact a topological(?) proof of this statement and the following generalization, essentially due to Péter Csikvári (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$.

Prop. 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. Finally, observe that any path in $G$ lifts to a matching in $H$ in exactly two ways, where $H$ is any double cover. 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.


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.


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.