PreprintarXiv licencearXiv
The Stable Marriage Polytope is Box-Totally Dual Integral
Abstract
A stable matching in a bipartite preference system is a matching that has no unmatched pair whose endpoints both prefer each other to their current assignments. Rothblum gave a linear description of the stable marriage polytope, the convex hull of the incidence vectors of stable matchings. We prove that this polytope is box-totally dual integral. The proof uses the affine representation of the stable marriage polytope as an order polytope together with the matricial characterization of box-TDI polyhedra. Since Kiraly and Pap proved that Rothblum's description is totally dual integral, our result further implies that Rothblum's system is box-totally dual integral.
Related
- A Quadratic Lower Bound for the Shield Number of the Stable Marriage Problem: Rearrangement, Extremal Construction, and Biclique Realizability
- Integral curvature estimates and geodesic limits for stable abelian Higgs fields
- Stable base change from unitary groups in three variables and integral relation of automorphic periods
- Non-symmetric integral geometry: alternative reconstruction procedure with dual Radon transform
- Dual Representations and Proxy Characterization of H2 Norm for Partial Integral Equations
BibTeX
@misc{barbato2026stable,
title = {{The Stable Marriage Polytope is Box-Totally Dual Integral}},
author = {Michele Barbato and Emiliano Lancini},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.12720},
eprint = {2610.12720},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.12720},
}
RIS
TY - UNPB
TI - The Stable Marriage Polytope is Box-Totally Dual Integral
AU - Michele Barbato
AU - Emiliano Lancini
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.12720
UR - https://arxiv.org/abs/2610.12720
AB - A stable matching in a bipartite preference system is a matching that has no unmatched pair whose endpoints both prefer each other to their current assignments. Rothblum gave a linear description of the stable marriage polytope, the convex hull of the incidence vectors of stable matchings. We prove that this polytope is box-totally dual integral. The proof uses the affine representation of the stable marriage polytope as an order polytope together with the matricial characterization of box-TDI polyhedra. Since Kiraly and Pap proved that Rothblum's description is totally dual integral, our result further implies that Rothblum's system is box-totally dual integral.
ER -