Variations sur le thème E+ E = XY (Variations on the theme E+ E = XY)

DOI10.1016/S0196-8858(02)00010-6MaRDI QIDQ1865262zbMATH OpenFDO

Authors Bodo Lass

Publication date 26 March 2003

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0196-8858(02)00010-6

zbMATH Keywords

complementary graphcover polynomialgenerating functionsHamiltonian circuitRook polynomialRédei's theoremsymmetric functionstournament

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Symmetric functions and generalizations (05E05)

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.

Recommendations

• The algebra of set functions. II: An enumerative analogue of Hall's theorem for bipartite graphs
• A class of `matching-equivalent' bipartite graphs
• scientific article; zbMATH DE number 4196005
• Matching polynomials and duality
• Another short proof of the Joni-Rota-Godsil integral formula for counting bipartite matchings

Cites work

• A short proof of the rook reciprocity theorem
• A symmetric function generalization of the chromatic polynomial of a graph
• A vector space analog of permutations with restricted position
• Acyclic orientations and the chromatic polynomial
• Convolution structures for Laguerre polynomials
• Derangements and Laguerre polynomials
• Hermite polynomials and a duality relation for matchings polynomials
• scientific article; zbMATH DE number 1577992 (Why is no real title available?)
• scientific article; zbMATH DE number 3645097 (Why is no real title available?)
• scientific article; zbMATH DE number 3127542 (Why is no real title available?)
• scientific article; zbMATH DE number 3841894 (Why is no real title available?)
• scientific article; zbMATH DE number 3941543 (Why is no real title available?)
• scientific article; zbMATH DE number 3766017 (Why is no real title available?)
• scientific article; zbMATH DE number 3517193 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 487720 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• scientific article; zbMATH DE number 3285977 (Why is no real title available?)
• scientific article; zbMATH DE number 3303831 (Why is no real title available?)
• scientific article; zbMATH DE number 3344586 (Why is no real title available?)
• scientific article; zbMATH DE number 3420754 (Why is no real title available?)
• Laguerre polynomials and derangements
• Laguerre Polynomials, Weighted Derangements, and Positivity
• On the cover polynomial of a digraph
• Permutation Problems and Special Functions
• Problems in algebraic combinatorics
• Rook Theory. I.: Rook Equivalence of Ferrers Boards
• The cycle-path indicator polynomial of a digraph
• The number of open chains of length three and the parity of the number of open chains of length k in self-complementary graphs
• The path-cycle symmetric function of a digraph
• Weighted permutation problems and Laguerre polynomials

Cited in

(7)

• Mehler formulae for matching polynomials of graphs and independence polynomials of clawfree graphs
• CUMULANTS IN NONCOMMUTATIVE PROBABILITY THEORY III: CREATION AND ANNIHILATION OPERATORS ON FOCK SPACES
• Further Variants of Gutman's Formulas
• The algebra of set functions. II: An enumerative analogue of Hall's theorem for bipartite graphs
• The algebra of set functions. I: The product theorem and duality
• Revisiting the Rédei-Berge symmetric functions via matrix algebra
• Set maps, umbral calculus, and the chromatic polynomial

This page was built for publication: Variations sur le thème \({E+\overline {E} = XY}\) (Variations on the theme \({E+\overline {E} = XY})\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1865262)