Balancing pairs and the cross product conjecture

DOI10.1007/BF01110378zbMath0839.06002WikidataQ29027177 ScholiaQ29027177MaRDI QIDQ1908931

Graham R. Brightwell, Stefan Felsner, William T. jun. Trotter

Publication date: 19 June 1996

Published in: Order (Search for Journal in Brave)

zbMATH Keywords

sortingpartially ordered setlinear extensionAhlswede-Daykin inequalitybalancing pairscross product conjecture

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07)

Related Items

A family of partially ordered sets with small balance constant, The cross-product conjecture for width two posets, Multivariate correlation inequalities for \(P\)-partitions, A combinatorial approach to height sequences in finite partially ordered sets, Sorting probability for large Young diagrams, Order-invariant measures on causal sets, Sorting under partial information (without the ellipsoid algorithm)., Antimatroids and balanced pairs, Counting linear extension majority cycles in partially ordered sets on up to 13 elements, The gold partition conjecture, On the \(1/3-2/3\) conjecture, Improving the \(\frac{1}{3}\)-\(\frac{2}{3}\) conjecture for width two posets, On Generalized Comparison-Based Sorting Problems, Balanced pairs in partial orders

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Events correlated with respect to every subposet of a fixed poset
• Linear extensions of infinite posets
• Balancing extensions via Brunn-Minkowski
• Balance theorems for height-2 posets
• How good is the information theory bound in sorting?
• A strange pigeon-hole principle
• Semiorders and the 1/3-2/3 conjecture
• Balancing poset extensions
• A correlational inequality for linear extensions of a poset
• The Information-Theoretic Bound is Good for Merging
• The FKG Inequality and Some Monotonicity Properties of Partial Orders
• The 1/3–2/3 Conjecture for 5-Thin Posets
• A Note on Poset Geometries
• An inequality for the weights of two families of sets, their unions and intersections