Cycles and perfect matchings Original Research Article

Fan Chung and Ron Graham (J. Combin. Theory Ser. B 65 (1995) 273–290) introduced the cover polynomial for a directed graph and showed that it was connected with classical rook theory. Dworkin (J. Combin. Theory Ser. B 71 (1997) 17–53) showed that the cover polynomial naturally factors for directed graphs associated with Ferrers boards. The authors (Adv. Appl. Math. 27 (2001) 438–481) developed a rook theory for shifted Ferrers boards where the analogue of a rook placement is replaced by a partial perfect matching of K2n, the complete graph on 2n vertices. In this paper, we show that an analogue of Dworkinʹs result holds for shifted Ferrers boards in this setting. We also show how cycle-counting matching numbers are connected to cycle-counting “hit numbers” (which involve perfect matchings of K2n).