Enumeration of Matchings — Problem 17

Definitions and mathematical statement

For a finite graph $G=(V,E)$, a matching is a subset $M\subseteq E$ whose edges have pairwise disjoint endpoint sets. A perfect matching is a matching incident with every vertex. Given edge weights $w:E\to R$ in a specified commutative coefficient ring $R$, define \[ Z_{\mathrm{all}}(G,w)=\sum_{M\text{ a matching of }G}\prod_{e\in M}w(e),\qquad Z_{\mathrm{perfect}}(G,w)=\sum_{M\text{ a perfect matching of }G}\prod_{e\in M}w(e), \] with empty products equal to $1$. These definitions provide two possible interpretations of the weighted sum in the supplied excerpt; the excerpt does not specify which convention is intended. The finite graph setting and coefficient ring likewise require confirmation.

A local substitution replaces a weighted subgraph by another weighted subgraph, with specified attachments to the rest of the graph. The request attributed to Propp is to characterize those local substitutions that have a predictable effect on the weighted sum of matchings of a graph. The supplied excerpt does not define the allowable substitutions or the meaning of a predictable effect, so it does not determine a unique formal classification problem.

The first substitution displayed in the source is described there as the most useful one so far. Its unmarked edges have weight $1$, and its new weights satisfy \[ A=\frac{a}{ac+bd},\qquad B=\frac{b}{ac+bd},\qquad C=\frac{c}{ac+bd},\qquad D=\frac{d}{ac+bd}. \] These expressions require $ac+bd$ to be invertible in the chosen coefficient ring; over a field, this requires $ac+bd\ne0$. The source does not specify the weight domain or a treatment of the singular case. Its extracted diagram does not unambiguously specify the incidence relations, attachment vertices, or edge weight placements, so a complete graph replacement cannot be recovered reliably from the supplied text.

The source also credits Rick Kenyon with a useful substitution. Its extracted diagram contains vertex labels $p,q,r,s,t,u$ and numerical weight labels $3/2,1/2,2$, but their placement is not reliably recoverable. The accompanying restriction must be retained: vertices $p,q,t,u$ may be attached elsewhere in the graph, whereas $r,s$ may not. The excerpt supplies no explicit formula for the resulting change in the weighted sum.

Both displayed substitutions are therefore motivating examples whose precise diagrams require recovery before they can serve as fully specified mathematical instances. The registry labels this problem open; that label is supplied metadata, not an independently verified mathematical assessment.

Short English statement

Propp asks which local replacements in a weighted graph have a predictable effect on its matching sum. The supplied excerpt leaves the matching convention and the meaning of predictability unspecified, and its extracted example diagrams are ambiguous. Kenyon's example explicitly permits external attachments at $p,q,t,u$, but forbids them at $r,s$.

Sources

• Local UnsolvedMath registry, permanent ID $800346$, source problem code catalogue entry, title Enumeration of Matchings --- Problem 17; set: AMR Open Problem Lists. The supplied record attributes the problem to Propp, gives the proposed year as 1998, and labels its status open. Supplied upstream revision: d371ee917ac9647fbb06cd6fc529deec6f3dda82.
• Propp, Twenty Open Problems in Enumeration of Matchings (1998), Problem 17 (#17). Supplied source URL: https://arxiv.org/abs/math/9801060. The record reports access on 2026-10-16 and extraction by arxiv_latex; these are supplied provenance details, not a claim of independent source access or verification.
• The supplied excerpt attributes the second local substitution to Rick Kenyon. No separate reference for that substitution is supplied. The description of the first substitution as the most useful one so far, and of Kenyon's substitution as useful, is source-specific commentary rather than a new assessment.