Variations sur le thème \({E+\overline {E} = XY}\) (Variations on the theme \({E+\overline {E} = XY})\)
type: Item
instance of: scholarly article
title: Variations sur le thème \({E+\overline {E} = XY}\) (Variations on the theme \({E+\overline {E} = XY})\)
zbMATH Open document ID: 1015.05005
DOI: 10.1016/S0196-8858(02)00010-6
author: Bodo Lass
published in: Advances in Applied Mathematics
publication date: 2003-03-26T00:00:00Z
review text: 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.
reviewed by: Clemens Heuberger
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05E35
Mathematics Subject Classification ID: 05E05
zbMATH DE Number: 1888311
zbMATH Keywords: Rook polynomial
zbMATH Keywords: complementary graph
zbMATH Keywords: Hamiltonian circuit
zbMATH Keywords: cover polynomial
zbMATH Keywords: tournament
zbMATH Keywords: Rédei's theorem
zbMATH Keywords: symmetric functions
zbMATH Keywords: generating functions
MaRDI profile type: Publication
cites work: Q3050437
cites work: The cycle-path indicator polynomial of a digraph
cites work: Convolution structures for Laguerre polynomials
cites work: Permutation Problems and Special Functions
cites work: Weighted permutation problems and Laguerre polynomials
cites work: Q3312256
cites work: Q4097320
cites work: A short proof of the rook reciprocity theorem
cites work: The path-cycle symmetric function of a digraph
cites work: On the cover polynomial of a digraph
cites work: Q5685088
cites work: Derangements and Laguerre polynomials
cites work: Q5620607
cites work: Laguerre Polynomials, Weighted Derangements, and Positivity
cites work: Problems in algebraic combinatorics
cites work: Hermite polynomials and a duality relation for matchings polynomials
cites work: Rook Theory. I.: Rook Equivalence of Ferrers Boards
cites work: Laguerre polynomials and derangements
cites work: A vector space analog of permutations with restricted position
cites work: Q2704226
cites work: Acyclic orientations and the chromatic polynomial
cites work: Q4276003
cites work: Q3947818
cites work: Q5585195
cites work: The number of open chains of length three and the parity of the number of open chains of length k in self-complementary graphs
cites work: Q3243274
cites work: Q3714083
cites work: A symmetric function generalization of the chromatic polynomial of a graph
cites work: Q4344108
cites work: Q4236280
cites work: Q5569398
description: scientific article; zbMATH DE number 1888311