On log concavity for order-preserving maps of partial orders

DOI10.1016/0012-365X(84)90049-9MaRDI QIDQ795043zbMATH OpenOpenAlexFDO

Authors Jacqueline W. Daykin, Michael S. Paterson, David E. Daykin

Publication date 1984

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(84)90049-9

zbMATH Keywords

Aleksandrov-Fenchel inequalitieslog concave sequencestrict order- preserving maps

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Partial orders, general (06A06)

Review text

\textit{R. P. Stanley} [J. Comb. Theory, Ser. A 31, 56-65 (1981; Zbl 0484.05012)] used the Aleksandrov-Fenchel inequalities from the theory of mixed volumes to prove the following result. Let P be a partially ordered set with n elements, and let \(x\in P\). If \(N^*_ i\) is the number of linear extensions \(\lambda:P\to \{1,2,...,n\}\) satisfying \(\lambda(x)=i\), then the sequence \(N^*_ 1,...,N^*_ n\) is log concave (and therefore unimodal). Here the analogous results for both strict order- preserving and order-preserving maps are proved using an explicit injection. Further, if \(v_ c\) is the number of strict order-preserving maps of P into a chain of length c, then \(v_ c\) is shown to be log concave, and the corresponding result is established for order-preserving maps.

Recommendations

• Inequalities for the number of monotonic functions of partial orders
• Two poset polytopes
• A combinatorial approach to height sequences in finite partially ordered sets
• A recurrence for linear extensions
• Order Preserving Maps and Linear Extensions of a Finite Poset

Cites work

• An inequality for the weights of two families of sets, their unions and intersections
• Combinatorial applications of an inequality from statistical mechanics
• Correlation inequalities on some partially ordered sets
• scientific article; zbMATH DE number 3645097 (Why is no real title available?)
• scientific article; zbMATH DE number 3140980 (Why is no real title available?)
• scientific article; zbMATH DE number 3771663 (Why is no real title available?)
• scientific article; zbMATH DE number 3893259 (Why is no real title available?)
• scientific article; zbMATH DE number 3313379 (Why is no real title available?)
• On Unimodality for Linear Extensions of Partial Orders
• Two combinatorial applications of the Aleksandrov-Fenchel inequalities

Cited in

(12)

• Two poset polytopes
• Inductive and injective proofs of log concavity results
• Order-preserving maps from a poset to a chain, the order polytope, and the Todd class of the associated toric variety.
• Inequalities for the number of monotonic functions of partial orders
• Logarithmic submajorisation and order-preserving linear isometries
• Order Preserving Maps and Linear Extensions of a Finite Poset
• scientific article; zbMATH DE number 4035884 (Why is no real title available?)
• Progress in selection
• Effective Poset Inequalities
• Multivariate correlation inequalities for \(P\)-partitions
• A combinatorial approach to height sequences in finite partially ordered sets
• Equality cases of the Alexandrov-Fenchel inequality are not in the polynomial hierarchy

This page was built for publication: On log concavity for order-preserving maps of partial orders

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