Total non-negativity of some combinatorial matrices

DOI10.1016/J.JCTA.2019.105179MaRDI QIDQ2299628zbMATH OpenOpenAlexWikidataFDO

Authors David Galvin, Adrian Pacurar

Publication date 21 February 2020

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

Full work available at URL https://arxiv.org/abs/1807.08658

zbMATH Keywords

chordal graphsgraph Stirling numbersLah numbersLindström's lemmaplanar networksrook numbersStirling numberstotal non-negativity

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Bell and Stirling numbers (11B73) Special matrices (15B99)

Abstract: Many combinatorial matrices --- such as those of binomial coefficients, Stirling numbers of both kinds, and Lah numbers --- are known to be totally non-negative, meaning that all minors (determinants of square submatrices) are non-negative. The examples noted above can be placed in a common framework: for each one there is a non-decreasing sequence $(a_1,a_2,ldots)$, and a sequence $(e_1,e_2,ldots)$, such that the $(m,k)$-entry of the matrix is the coefficient of the polynomial $(x-a_1)cdots(x-a_k)$ in the expansion of $(x-e_1)cdots(x-e_m)$ as a linear combination of the polynomials $1,x-a_1,ldots,(x-a_1)cdots(x-a_m)$. We consider this general framework. For a non-decreasing sequence $(a_1,a_2,ldots)$ we establish necessary and sufficient conditions on the sequence $(e_1,e_2,ldots)$ for the corresponding matrix to be totally non-negative. As corollaries we obtain totally non-negativity of matrices of rook numbers of Ferrers boards, and of graph Stirling numbers of chordal graphs.

Recommendations

• Totally non-negativity of a family of change-of-basis matrices
• Combinatorics and total positivity
• Total positivity of recursive matrices
• On total positivity of Catalan-Stieltjes matrices
• Inequalities in products of minors of totally nonnegative matrices

Cites work

• \(\sigma\)-polynomials and graph coloring
• \(k\)-complementing subsets of nonnegative integers
• A unified approach to generalized Stirling numbers
• Applications of chromatic polynomials involving Stirling numbers
• Bell and Stirling numbers for graphs
• Combinatorially interpreting generalized Stirling numbers
• Combinatorics and total positivity
• Connections between the matching and chromatic polynomials
• Expansions of Chromatic Polynomials and Log-Concavity
• scientific article; zbMATH DE number 1113632 (Why is no real title available?)
• scientific article; zbMATH DE number 1136361 (Why is no real title available?)
• scientific article; zbMATH DE number 3368554 (Why is no real title available?)
• Inverses of triangular matrices and bipartite graphs
• Jacobi-Stirling numbers, Jacobi polynomials, and the left-definite analysis of the classical Jacobi differential expression
• Location of Zeros of Chromatic and Related Polynomials of Graphs
• On \(xD\)-generalizations of Stirling numbers and Lah numbers via graphs and rooks
• On the Vector Representations of Induced Matroids
• Restricted Stirling and Lah number matrices and their inverses
• Rook Theory. I.: Rook Equivalence of Ferrers Boards
• Rook theory. III: Rook polynomials and the chromatic structure of graphs
• Stirling numbers of forests and cycles
• Total positivity of recursive matrices
• Total positivity of Riordan arrays
• Total positivity: tests and parametrizations.
• Two approaches to normal order coefficients

Cited in

(15)

• Combinatorial results on completely positive matrices
• Lah numbers and Lindström's lemma
• Combinatorics and total positivity
• Proof of a conjecture on the total positivity of amazing matrices
• Positivity properties of some special matrices
• Analytic combinatorics of coordination numbers of cubic lattices
• scientific article; zbMATH DE number 1136361 (Why is no real title available?)
• Total positivity of a shuffle matrix
• On Nonnegative Integer Matrices and Short Killing Words
• Recent developments in combinatorial aspects of normal ordering
• Totally non-negativity of a family of change-of-basis matrices
• Coefficientwise total positivity and Stieltjes moment properties from Riordan arrays
• On total positivity of Catalan-Stieltjes matrices
• On the totally positive matrices related to refined Eulerian numbers
• Trees, forests, and total positivity. I: \(q\)-trees and \(q\)-forests matrices

This page was built for publication: Total non-negativity of some combinatorial matrices

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