Prime factorisation of stable-matching instances: uniqueness, simultaneous products, and an exact census
Abstract
Every balanced instance of the stable marriage problem with strict complete preferences has a unique finest partition into prime blocks, and that single partition simultaneously factors three different structures: the reachable execution digraph as a Cartesian product, the proposal-prefix antimatroid as a direct sum, and the stable-matching lattice as a direct product. The converse fails, and fails at every size from two on: two explicit families share the identical Boolean-cube execution while one is maximally decomposable with a single stable matching and the other is prime with n. Uniqueness yields an exact census, a recursion counting the prime instances at every size, under which exactly 88,478,208 of the 110,075,314,176 profiles with four agents on each side are decomposable and the decomposable fraction is asymptotically n! / n^(2n). The blocks are characterised as the square components of the mutual-rank filtration, so the partition is computable in polynomial time and the factorisation is a tool rather than only a fact.
Related
- On a fundamental obstruction in the Derscariu Programme: Failure of Dixmier trace factorisation on infinite tensor products of Toeplitz algebras
- Uniqueness sets in weighted ℓ2-spaces via simultaneous approximation
- Factorisation and matrix amplification of real rank zero inclusions
- The Uniform Primary Factorisation Property for C(K,E)
- Improved upper bounds for five IHTC-2024 benchmark instances via exact reoptimization of the nurse-to-room layer
BibTeX
@misc{ishida2026prime,
title = {{Prime factorisation of stable-matching instances: uniqueness, simultaneous products, and an exact census}},
author = {Yoshiteru Ishida},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.05617},
eprint = {2610.05617},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.05617},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Prime factorisation of stable-matching instances: uniqueness, simultaneous products, and an exact census
AU - Yoshiteru Ishida
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2610.05617
UR - https://arxiv.org/abs/2610.05617
AB - Every balanced instance of the stable marriage problem with strict complete preferences has a unique finest partition into prime blocks, and that single partition simultaneously factors three different structures: the reachable execution digraph as a Cartesian product, the proposal-prefix antimatroid as a direct sum, and the stable-matching lattice as a direct product. The converse fails, and fails at every size from two on: two explicit families share the identical Boolean-cube execution while one is maximally decomposable with a single stable matching and the other is prime with n. Uniqueness yields an exact census, a recursion counting the prime instances at every size, under which exactly 88,478,208 of the 110,075,314,176 profiles with four agents on each side are decomposable and the decomposable fraction is asymptotically n! / n^(2n). The blocks are characterised as the square components of the mutual-rank filtration, so the partition is computable in polynomial time and the factorisation is a tool rather than only a fact.
ER -