Id: arxiv/2608.22308 Url: https://arxiv.org/abs/2608.22308 Tags: math.CO, cond-mat.stat-mech, math-ph, math.PR Score: 0 Title: Spanning trees in the Assignment Problem: two theorems and two conjectures Domain: math.CO Source: arxiv Authors: Sergio Caracciolo, Gabriele Sicuro, Andrea Sportiello Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-08-23 Page: https://delphi.science/r/arxiv/2608.22308 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…