Effective poset inequalities

Abstract

We explore inequalities on linear extensions of posets and make them effective in different ways. First, we study the Björner--Wachs inequality and generalize it to inequalities on order polynomials and their $q$-analogues via direct injections and FKG inequalities. Second, we give an injective proof of the Sidorenko inequality with computational complexity significance, namely that the difference is in $\#P$. Third, we generalize the Sidorenko inequality to posets with small chain intersections and give complexity theoretic applications.

arXiv comment36 pages, 1 figure. Added a reference to Daykin--Daykin--Paterson inequality that were previously presented as Conjecture 4.19 in v2

References in corpus (7)

• Combinatorial Markov chains on linear extensions
• Geometric Inequalities for Anti-Blocking Bodies
• Introduction to the combinatorial atlas
• Separable elements and splittings of Weyl groups
• Stanley's non-Ehrhart-positive order polytopes
• The hull metric on Coxeter groups
• Upper bounds on mixing time of finite Markov chains

Cited by in corpus (4)

• Equality cases of the Alexandrov--Fenchel inequality are not in the polynomial hierarchy
• The hull metric on Coxeter groups
• On the cross-product conjecture for the number of linear extensions
• Correlation inequalities for linear extensions