On the Neggers-Stanley conjecture and the Eulerian polynomials
type: Item
instance of: scholarly article
title: On the Neggers-Stanley conjecture and the Eulerian polynomials
zbMATH Open document ID: 0911.05005
published in: Journal of Combinatorial Theory. Series A
publication date: 1999-05-04T00:00:00Z
review text: If \(P=(P,<)\) is an \(n\)-poset (i.e., \(P\) contains \(n\) elements) and \(\lambda: P\to\{1,\dots, n\}\) is a labeling of the vertices of \(P\), then a permutation \(w\in S_n\) is \((P, \lambda)\)-compatible if \(\lambda^{-1}(w(i))<\lambda^{-1}(w(j))\) implies \(i<j\). For \(i\geq 1\), let \(d_i(P,\lambda)\) be the number of \((P,\lambda)\)-compatible permutations with \(i\) descents. The \(W\)-polynomial of \((P,\lambda)\) is defined as \(W(P,\lambda,t)=\sum_{i\geq 0}d_i(P, \lambda) t^{i+1}\). The Neggers-Stanley conjecture claims that \(W(P,\lambda,t)\) has only real zeros and by now there is a considerably body of information in its support. Thus, if \(P\) is an \(n\)-antichain \((n\)-set) implies \(W(P,\lambda,t) =A_n(t)\), the \(n\)th Eulerian polynomial, then the conjecture holds. In further support the author deduces that for graded \(n\)-posets of rank 1 or 2, when \(\lambda\) is a natural labeling \((u<v\) in \((P,<)\) implies \(\lambda(u)< \lambda(v))\), then \(W(P,\lambda,t)\) is unimodal, which is quite close to having real zeros when coefficients are non-negative integers as in this case. Also, via the simplicial complex associated with bounded \(n\)-posets and other structures the author is able to produce combinatorial proofs of several interesting known facts, including the observation that the Eulerian polynomials are both log-concave and unimodal.
reviewed by: J. Neggers
Mathematics Subject Classification ID: 05A99
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 05E99
zbMATH DE Number: 1212923
zbMATH Keywords: labeling
zbMATH Keywords: permutation
zbMATH Keywords: Neggers-Stanley conjecture
zbMATH Keywords: log-concave
zbMATH Keywords: unimodal
Wikidata QID: Q123021612
author: Vesselin Gasharov
MaRDI profile type: Publication
full work available at URL: jcta.1997.2839
OpenAlex ID: W2074351421
cites work: On the generating functions of totally positive sequences. I
cites work: Unimodal, log-concave and Pólya frequency sequences in combinatorics
cites work: Combinatorics and total positivity
cites work: Hilbert polynomials in combinatorics
cites work: \(h\)-shellings and \(h\)-complexes
cites work: Q4133984
cites work: Binomial determinants, paths, and hook length formulae
cites work: Q3800169
cites work: Q4347963
cites work: A multiindexed Sturm sequence of polynomials and unimodality of certain combinatorial sequences
cites work: Q3748279
cites work: Q4294628
cites work: Eulerian numbers, tableaux, and the Betti numbers of a toric variety
cites work: Enumeration of functions from posets to chains
DOI: 10.1006/JCTA.1997.2839
description: scientific article; zbMATH DE number 1212923