{"id":"arxiv/2610.05617","url":"https://arxiv.org/abs/2610.05617","tags":["cs.DS","cs.DM","cs.GT","math.CO"],"score":0,"title":"Prime factorisation of stable-matching instances: uniqueness, simultaneous products, and an exact census","domain":"cs.DS","source":"arxiv","authors":["Yoshiteru Ishida"],"reviews":0,"subject":"cs.DS","summary":"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.…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-04","reactions":{}}