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

What the math gives to ML

The paper constructs a sparse graph by taking the union of optimal bipartite matchings over a structured family of slightly modified assignment instances, and proves that this union is a spanning tree. A transferable asset is that a tree-supported transport plan can represent optimal transport between unequal-size empirical measures, with edge mass proportional to the number of perturbed optimal matchings using each edge. This suggests replacing dense cross-attention or token-to-token transport with a periodically recomputed tree support, yielding linear-edge sparse mixing while retaining a principled mass-conservation constraint.