Enumeration of Matchings — Problem 6

Definitions and mathematical statement

Let $G=(U\sqcup V,E)$ be a bipartite planar graph, with bipartite adjacency matrix $A$. For the finite balanced case $|U|=|V|=n$, a signing of $A$ is a matrix $K$ obtained by multiplying each nonzero entry of $A$ by $+1$ or $-1$. The source describes Kasteleyn matrices as signings for which all nonzero terms in the determinant expansion have the same sign. Whether this determinant condition is intended as a complete definition, or whether additional planar Kasteleyn conditions are required, is unresolved in the supplied record.

For a Kasteleyn matrix $K$ in the intended sense, let $K^*=\overline{K}^{\mathsf T}$ be its adjoint and set $H=KK^*$. Its spectrum is the multiset of its eigenvalues, counted with algebraic multiplicity; these eigenvalues are real and nonnegative. The source asserts that this multiset is independent of the choice of $K$, attributing independent proofs to David Wilson and Horst Sachs. This assertion is supplied background, whose precise hypotheses and proof are not included.

Problem (Propp, 1998, Problem 6). Determine the combinatorial significance of the spectrum of $KK^*$, where $K$ is any Kasteleyn matrix associated with a bipartite planar graph $G$. Under the asserted choice independence, seek an interpretation of this spectrum in terms of the combinatorial structure of $G$.

The source does not prescribe a particular kind of interpretation or a criterion for a complete answer. Finiteness and equal bipartition sizes are implicit in the displayed determinant formulation, rather than explicit hypotheses of the original question; the intended treatment of other graphs, parallel edges, and graphs without perfect matchings requires clarification. The stated choice independence should not be treated as established under the determinant condition alone without resolving these qualifications.

Short English statement

Propp asks what combinatorial information is represented by the eigenvalues of $KK^*$ for a Kasteleyn matrix of a bipartite planar graph. The source attributes independence from the choice of matrix to David Wilson and Horst Sachs, but leaves the precise hypotheses and intended meaning of combinatorial significance unspecified.

Sources

• Local UnsolvedMath registry, permanent ID $800335$, exact source problem code catalogue entry, title "Enumeration of Matchings --- Problem 6." The record attributes the problem to Propp, gives the proposed year as 1998, and labels it open; this is supplied registry status, not an independently verified current assessment.
• Propp, Twenty Open Problems in Enumeration of Matchings (1998), Problem 6 (#6), https://arxiv.org/abs/math/9801060. The supplied provenance records access on 2026-10-16 and extraction by arxiv_latex; these are supplied provenance details, not a claim of independent access or verification.
• The supplied excerpt attributes independent proofs of the asserted spectral invariance to David Wilson and Horst Sachs. No separate references for those proofs are supplied.