{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-23","reactions":{}}