The cross-product conjecture for width two posets

DOI10.1090/TRAN/8679MaRDI QIDQ5100036zbMATH OpenOpenAlexFDO

Authors Swee Hong Chan, Igor Pak, Greta Panova

Publication date 29 August 2022

Full work available at URL https://arxiv.org/abs/2104.09009

zbMATH Keywords

\(1/3\)-\(2/3\) conjecture\(q\)-analoguecross-product conjectureGraham-Yao-Yao inequalityKahn-Saks inequalitylattice pathLindström-Gessel-Viennot lemmalinear extensions of posetslog-concavityStanley inequalityXYZ inequality

Mathematics Subject Classification ID

Combinatorial inequalities (05A20) (q)-calculus and related topics (05A30) Combinatorics of partially ordered sets (06A07) Algebraic aspects of posets (06A11)

Abstract: The cross--product conjecture (CPC) of Brightwell, Felsner and Trotter (1995) is a two-parameter quadratic inequality for the number of linear extensions of a poset $P=(X,prec)$ with given value differences on three distinct elements in $X$. We give two different proofs of this inequality for posets of width two. The first proof is algebraic and generalizes CPC to a four-parameter family. The second proof is combinatorial and extends CPC to a $q$-analogue. Further applications include relationships between CPC and other poset inequalities, including a new $q$-analogue of the Kahn--Saks inequality.

Recommendations

• Improving the \(\frac{1}{3}\)-\(\frac{2}{3}\) conjecture for width two posets
• Balancing pairs and the cross product conjecture
• The 1/3–2/3 Conjecture for 5-Thin Posets
• Extensions of the Kahn-Saks inequality for posets of width two
• Counting linear extensions of restricted posets

Cites work

• A combinatorial approach to height sequences in finite partially ordered sets
• A correlational inequality for linear extensions of a poset
• A family of partially ordered sets with small balance constant
• Balancing pairs and the cross product conjecture
• Balancing poset extensions
• Combinatorial applications of the Hodge-Riemann relations
• Combinatorial Inequalities
• Correlation Among Partial Orders
• Counting linear extensions
• How good is the information theory bound in sorting?
• scientific article; zbMATH DE number 3821741 (Why is no real title available?)
• scientific article; zbMATH DE number 3963888 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 718851 (Why is no real title available?)
• Improving the \(\frac{1}{3}\)-\(\frac{2}{3}\) conjecture for width two posets
• Lorentzian polynomials
• Negative dependence and the geometry of polynomials
• On \(q\)-integrals over order polytopes
• Some Monotonicity Properties of Partial Orders
• Sorting probability for large Young diagrams
• Spectral lower bounds for the quantum chromatic number of a graph. II
• The FKG Inequality and Some Monotonicity Properties of Partial Orders
• The Information-Theoretic Bound is Good for Merging
• The probabilistic method
• The XYZ conjecture and the FKG inequality
• Two combinatorial applications of the Aleksandrov-Fenchel inequalities
• Unimodal, log-concave and Pólya frequency sequences in combinatorics

Cited in

(9)

• Extensions of the Kahn-Saks inequality for posets of width two
• Effective Poset Inequalities
• Enumerative combinatorics. Abstracts from the workshop held December 11--17, 2022
• Log-concave poset inequalities (extended abstract)
• Multivariate correlation inequalities for \(P\)-partitions
• Log-concave poset inequalities
• Correlation inequalities for linear extensions
• On the cross-product conjecture for the number of linear extensions
• Skew shapes, Ehrhart positivity, and beyond

This page was built for publication: The cross-product conjecture for width two posets

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