MathCastle
Graph TheoryHardBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Hard problem

Men A,B,CA,B,C rank women X,Y,ZX,Y,Z as A ⁣: ⁣Y,Z,XA\!:\!Y,Z,X; B ⁣: ⁣Y,X,ZB\!:\!Y,X,Z; C ⁣: ⁣Z,Y,XC\!:\!Z,Y,X. Women rank men as X ⁣: ⁣A,B,CX\!:\!A,B,C; Y ⁣: ⁣C,B,AY\!:\!C,B,A; Z ⁣: ⁣B,C,AZ\!:\!B,C,A. How many different stable matchings does this preference profile admit?