MathCastle
Graph TheoryHardBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Hard problem

Men 1,2,3,41,2,3,4 rank women cyclically: 1:A,B,C,D1: A,B,C,D;   2:B,C,D,A\;2: B,C,D,A;   3:C,D,A,B\;3: C,D,A,B;   4:D,A,B,C\;4: D,A,B,C. Women rank men cyclically too: A:2,3,4,1A: 2,3,4,1;   B:3,4,1,2\;B: 3,4,1,2;   C:4,1,2,3\;C: 4,1,2,3;   D:1,2,3,4\;D: 1,2,3,4. Among all 2424 possible perfect matchings of these 44 men to these 44 women, how many are stable (have no blocking pair)?