5 papers
Prime factorisation of stable-matching instances: uniqueness, simultaneous products, and an exact census
Yoshiteru Ishida
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 fa…
A Reachable-State Operator Formulation of Deferred Acceptance: Progress Invariants and Structural Diagnostics
Yoshiteru Ishida
We give a reachable-state operator formulation of one-to-one deferred acceptance with strict, possibly incomplete preference lists. A local update operator is defined for each acti…
A Quadratic Lower Bound for the Shield Number of the Stable Marriage Problem: Rearrangement, Extremal Construction, and Biclique Realizability
Yoshiteru Ishida
We study the Shield number of the stable marriage problem, defined as the minimum, over all preference profiles of size n, of the maximum number of blocking pairs attainable by a c…
Regular anti-phase templates in the stable marriage problem: a generator criterion, its converse, and a counting bound
Yoshiteru Ishida
We study a family of highly symmetric instances of the stable marriage problem built from regular actions of finite groups. Given a finite group G of order n and an ordering A of i…
Euler Constraints and the Cubic Criticality of Complete Bipartite Preference Structures
Yoshiteru Ishida
We introduce a polyhedral realizability problem for complete bipartite preference structures, the two-sided strict preference profiles that underlie the stable marriage problem. Gi…