Factorization of the cover polynomial

DOI10.1006/JCTB.1997.1745MaRDI QIDQ1386473zbMATH OpenOpenAlexFDO

Authors Morris Dworkin

Publication date 5 October 1998

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jctb.1997.1745

zbMATH Keywords

cover polynomialrook polynomial

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

The cover polynomial, as introduced by \textit{F. R. K. Chung} and \textit{R. L. Graham} [J. Comb. Theory, Ser. B 65, No. 2, 273-290 (1995; Zbl 0839.05045)], generalizes the factorial rook polynomial to two variables, by also encoding information about the partial permutations which correspond to rook placements. It is a well-known fact due to \textit{J. R. Goldman, J. T. Joichi} and \textit{D. E. White} [Proc. Am. Math. Soc. 52, 485-492 (1975; Zbl 0312.05002)] that the factorial rook polynomial of any Ferrers board, or, more generally, of any permutation of the columns of a Ferrers board (called skyline board by the author), factors completely into linear factors. The purpose of the article under review is to examine how much of this can be extended to the cover polynomial. The author shows that there is a straightforward extension to increasing Ferrers boards. The cover polynomial of a decreasing Ferrers board factors as well, although the analysis in this case is much more difficult. For arbitrary skyline boards there is no complete factorization into linear factors anymore. Still, through a very tricky analysis, the author establishes a (partial) factorization theorem in this case as well. The paper closes with factorization theorems for the cover polynomial of column-permuted staircase boards.

Recommendations

• Augmented rook boards and general product formulas
• Cycles and perfect matchings.
• Generalized rook polynomials

Cites work

• scientific article; zbMATH DE number 3983158 (Why is no real title available?)
• scientific article; zbMATH DE number 3344586 (Why is no real title available?)
• On the cover polynomial of a digraph
• Rook theory and hypergeometric series
• Rook Theory. I.: Rook Equivalence of Ferrers Boards
• Sur les partitions non croisées d'un cycle. (The non-crossed partitions of a cycle)
• The path-cycle symmetric function of a digraph

Cited in

(6)

• The combinatorics behind number-theoretic sieves
• Cycles and perfect matchings.
• Further investigation involving rook polynomials with only real zeros
• The drop polynomial of a weighted digraph
• scientific article; zbMATH DE number 4150221 (Why is no real title available?)
• Rook theory and cycle-counting permutation statistics

This page was built for publication: Factorization of the cover polynomial

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