The Unique Ground State

The monomer-dimer model on a graph asks: select a subset of edges (dimers) and vertices (monomers) so that each vertex participates in at most one, and maximize the total weight. On a finite graph, the optimal solution might not be unique — multiple matchings can achieve the same weight. On an infinite random tree, with random weights on both edges and vertices, the ground state is almost surely unique.

The proof works on unimodular Bienaymé-Galton-Watson trees — random trees where the offspring distribution is arbitrary but the root sees the same statistics as any other vertex (unimodularity). Edge weights and vertex weights are drawn independently from continuous distributions.

Uniqueness implies locality: the optimal assignment of a vertex (monomer or part of a dimer) depends only on its local neighborhood. More precisely, for any sequence of finite random graphs that converges locally to the infinite random tree, the ground states of the finite graphs converge locally to the ground state of the tree.

This has a strong decorrelation consequence. On the tree, the optimal assignments of two vertices become independent as their distance grows. The ground state has no long-range order — even though the optimization problem is global (maximizing total weight), the solution is determined by local information.

The continuity assumption on the weight distribution is essential. If weights can be equal (discrete distributions), ties create degeneracies where the ground state is non-unique and correlations can extend to arbitrary distances. Continuous weights break ties with probability one, and this tie-breaking is what forces uniqueness and locality.