Metraipolis › archive › dc_55c87fb7927d
Prime factorisation of stable-matching instances: uniqueness, simultaneous products, and an exact census — arXiv:2610.05617
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.05617
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-06T16:53:31.307Z
- SHA-256 of the archived text
b507d589fecbb49810053ac709d17b5c957b4917b472411ac5e9fbab9b949820- Stable URL of this page
https://metraipolis.com/documento/dc_55c87fb7927d
How to cite
Prime factorisation of stable-matching instances: uniqueness, simultaneous products, and an exact census — arXiv:2610.05617 — arXiv (en), https://arxiv.org/abs/2610.05617 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_55c87fb7927d (Metraipolis archive dc_55c87fb7927d, sha256 b507d589fecbb49810053ac709d17b5c957b4917b472411ac5e9fbab9b949820)
BibTeX
@misc{dc55c87fb7927d,
title = {Prime factorisation of stable-matching instances: uniqueness, simultaneous products, and an exact census — arXiv:2610.05617},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.05617},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_55c87fb7927d; sha256 b507d589fecbb49810053ac709d17b5c957b4917b472411ac5e9fbab9b949820},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.05617. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno). Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Combinatorics (math.CO). Pagina del lavoro: https://arxiv.org/abs/2610.05617 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-06T15:19:20.071Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).