Spanning trees in the Assignment Problem: two theorems and two conjectures

Abstract

The \emph{Minimum Matching Problem} consists of finding an independent edge set of minimum weight $M_{\star}(G)$ in a given edge-weighted graph $G$. When $G$ is bipartite, this reduces to the \emph{Assignment Problem}. We consider a variant of this problem defined by taking the union of optimal matchings across various slightly modified versions of the base graph: $H_{\mathcal{J}}(G)=\bigcup_{U \in \mathcal{J}} M_{\star}(G_{U})$. We establish two families of results: (1) In two distinct settings for the Assignment Problem, we prove that the resulting graphs $H_{\mathcal{J}}$, as well as certain associated graphs $\bar{H}_{\mathcal{J}}$, are spanning trees on the relevant base graphs $G$ and $\bar{G}$. (2) In these same settings, assuming the edge weights are given by the $p$-th power of Euclidean distances for point configurations in the plane, we show that for $p=1$ the tree $H_{\mathcal{J}}$ is non-crossing (i.e., its planar embedding has no crossing edges), whereas, remarkably, for $p=2$ the associated tree $\bar{H}_{\mathcal{J}}$ is non-crossing. Finally, we introduce novel conjectures in Statistical Mechanics, to be explored in future work: in the Random Euclidean Assignment Problem (where points are i.i.d.\ on a planar domain), we conjecture that for $p=2$ the trees $\bar{H}_{\mathcal{J}}$ are asymptotically distributed as Uniform Spanning Trees with free and wired boundary conditions in the two respective settings. In particular, suitable paths on the tree in the second setting, and on its planar dual in the first setting, are asymptotically distributed as $\text{SLE}_{\kappa}$ with $\kappa=2$.