MathCastle
Graph TheoryChallengeBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Challenge problem

Men A,B,C,DA,B,C,D rank women W,X,Y,ZW,X,Y,Z as A ⁣: ⁣X,W,Z,YA\!:\!X,W,Z,Y; B ⁣: ⁣W,Z,Y,XB\!:\!W,Z,Y,X; C ⁣: ⁣Z,Y,W,XC\!:\!Z,Y,W,X; D ⁣: ⁣Z,Y,X,WD\!:\!Z,Y,X,W. Women rank men as W ⁣: ⁣A,C,D,BW\!:\!A,C,D,B; X ⁣: ⁣C,A,B,DX\!:\!C,A,B,D; Y ⁣: ⁣B,D,A,CY\!:\!B,D,A,C; Z ⁣: ⁣B,C,A,DZ\!:\!B,C,A,D. How many different stable matchings does this preference profile admit?