A combinatorial approach to height sequences in finite partially ordered sets

DOI10.1016/J.DISC.2010.12.020MaRDI QIDQ629196zbMATH OpenOpenAlexFDO

Authors Csaba Biró, William T. Trotter

Publication date 8 March 2011

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2010.12.020

zbMATH Keywords

correlation inequalityheight sequencelinear extensionlog-concavity

Mathematics Subject Classification ID

Combinatorial inequalities (05A20) Combinatorics of partially ordered sets (06A07) Combinatorial probability (60C05)

Review text

Given an element \(x\) of a finite partially ordered set \(P\), the \(i\)th entry of the height sequence associated to \(x\) records the number of linear extensions of \(P\) in which position \(i\) is occupied by \(x\). Using the Alexandrov-Fenchel inequalities for mixed volumes of convex bodies, \textit{R. P. Stanley} [J. Comb. Theory, Ser. A 31, 56--65 (1981; Zbl 0484.05012)] showed that every height sequence is log-concave. A combinatorial proof of this result is given in the paper under review in the special case in which the set of elements of \(P\) which are incomparable to \(x\) is either a chain or a two-element antichain.

Recommendations

• On log concavity for order-preserving maps of partial orders
• Two poset polytopes
• Balance theorems for height-2 posets
• Balancing extensions via Brunn-Minkowski
• scientific article; zbMATH DE number 3977057

Cites work

• A combinatorial approach to correlation inequalities
• A correlational inequality for linear extensions of a poset
• A Monotonicity Property of Partial Orders
• An inequality for the weights of two families of sets, their unions and intersections
• Balancing pairs and the cross product conjecture
• Correlation inequalities on some partially ordered sets
• scientific article; zbMATH DE number 3893259 (Why is no real title available?)
• The FKG Inequality and Some Monotonicity Properties of Partial Orders
• The XYZ conjecture and the FKG inequality
• Two combinatorial applications of the Aleksandrov-Fenchel inequalities

Cited in

(7)

• Two poset polytopes
• Enumeration of series-parallel posets according to heights
• Linear extensions of ranked posets, enumerated by descents. A problem of Stanley from the 1981 Banff conference on ordered sets
• Hecke insertion and maximal increasing and decreasing sequences in fillings of stack polyominoes
• The height of a permutation and applications to distance between real line arrangements
• The cross-product conjecture for width two posets
• On log concavity for order-preserving maps of partial orders

This page was built for publication: A combinatorial approach to height sequences in finite partially ordered sets

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