Enumeration of Matchings — Problem 19

Definitions and mathematical statement

For each integer $n\geq 1$, let $Q_n=(V_n,E_n)$ be the cube graph with \[ V_n=\{0,2\}^{n},\qquad E_n=\left\{\{x,y\}:x,y\in V_n\text{ differ in exactly one coordinate}\right\}. \] Thus $Q_n$ is the graph of vertices and edges of an $n$-dimensional cube of side length $2$, and it has $2^n$ vertices. A perfect matching of $Q_n$ is a subset $M\subseteq E_n$ such that every vertex belongs to exactly one edge of $M$. Write \[ m_n=\left|\left\{M\subseteq E_n:M\text{ is a perfect matching of }Q_n\right\}\right|. \] Problem (Propp, 1998, Problem 19). Find a formula for $m_n$ valid for every integer $n\geq 1$.

The supplied source reports the initial values \[ m_1=1,\quad m_2=2,\quad m_3=9=3^2,\quad m_4=272=16\cdot17,\quad m_5=589185=3^2\cdot5\cdot13093. \] The source introduces this example in the context of bipartite graphs that need not be planar. It cautions that the enumeration problem may be intractable, observing that the number of vertices grows exponentially with $n$; this is a source qualification, not a stated complexity theorem. The requested type or computational efficiency of a formula is unspecified. The source does not address the zero-dimensional case; the statement above concerns the positive dimensions indicated by its examples.

Short English statement

Propp asks for a formula counting perfect matchings of the cube graph in every positive dimension. A perfect matching pairs all vertices along cube edges, using each vertex exactly once. The source leaves the intended form of the formula unspecified and cautions that the problem may be intractable because the graph has exponentially many vertices.

Sources

• Local UnsolvedMath registry: permanent ID $800348$, exact source problem code catalogue entry, title Enumeration of Matchings --- Problem 19. The supplied record attributes the problem to Propp, with proposed year $1998$.
• Propp, Twenty Open Problems in Enumeration of Matchings (1998), Problem 19 (#19). Supplied source URL: https://arxiv.org/abs/math/9801060.
• Supplied provenance records access on 2026-10-16 and extraction by arxiv_latex. These are supplied provenance details; no independent source access or verification is claimed. The registry labels the problem open; this is a supplied status, not an independently verified literature assessment.