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.

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

References in corpus (1)

• Introduction to the combinatorial atlas

Cited by in corpus (3)

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