Variations sur le thème \({E+\overline {E} = XY}\) (Variations on the theme \({E+\overline {E} = XY})\) (Q1865262)

Let \(G=(X\cup Y,E)\) be a bipartite graph and let \(p(G,r)\) be the number of \(r\)-matchings of \(G\). The bipartite complement is \(\overline G=(X\cup Y, \overline E)\), where \(\overline E=(X\times Y)\setminus E\). It is well known that the vector \((p(\overline G,r))_{r\geq 0}\) is completely determined by the vector \((p(G,r))_{r\geq 0}\). The author reproves this as well as related results (due to \textit{T. Chow} (and \textit{I. Gessel}) [A short proof of the rook reciprocity theorem, Electron. J. Comb. 3, Research paper R10 (1996); printed version J. Comb. 3, 121-122 (1996; Zbl 0852.05017)], and \textit{S. A. Joni} and \textit{G.-C. Rota} [J. Comb. Theory, Ser. A 29, 59-73 (1980; Zbl 0446.05004)]) and generalizes them using identities in an associated algebra of generating functions of set functions. A short proof of Berge's fundamental identity [Chemins hamiltoniens, ICC Research Report 67/2 (1967)] between Hamilton paths and circuits for oriented graphs follows from the general observations. Further consequences are the Chung-Graham [cf. \textit{F. R. K. Chung} and \textit{R. L. Graham}, J. Comb. Theory, Ser. B 65, 273-290 (1965; Zbl 0839.05045)] conjecture (first derived by \textit{T. Chow} [Adv. Math. 118, 71-98 (1996; Zbl 0847.05098)]) as well as Rédei's [\textit{L. Lovász}, Combinatorial problems and exercises (Akadémiai Kiadó, Budapest, and North-Holland, Amsterdam) (1993; Zbl 0785.05001)], and \textit{P. Camion}'s [Cah. Cent. Étud. Rech. Opér. 17, 175-183 (1975; Zbl 0331.05117)] and \textit{S. B. Rao}'s [Discrete Math. 28, 291-301 (1979; Zbl 0425.05036)] parity results for tournaments, non-oriented, and self-complementary graphs, respectively. Finally, relations between set functions and symmetric functions are studied; it is shown that the main theorem in Chow's PhD thesis [Symmetric functions, generalizations of graph polynomials, PhD thesis, MIT, 1995] becomes a direct consequence of Berge's identity.