The 1/3-2/3 conjecture for N-free ordered sets

zbMATH Open1288.06005arXiv1107.5626MaRDI QIDQ426908FDOQ426908

Authors: Imed Zaguia 

Publication date: 12 June 2012

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: A balanced pair in a finite ordered set $P=(V,leq)$ is a pair $(x,y)$ of elements of $V$ such that the proportion of linear extensions of $P$ that put $x$ before $y$ is in the real interval $[1/3,2/3]$. We prove that every finite $N$-free ordered set which is not totally ordered has a balanced pair.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Greedy balanced pairs in \(N\)-free ordered sets
• Balanced pairs in partial orders
• The 1/3-2/3 conjecture for ordered sets whose cover graph is a forest
• The 1/3–2/3 Conjecture for 5-Thin Posets
• A family of partially ordered sets with small balance constant

zbMATH Keywords

ordered setlinear extension\(1/3\)-\(2/3\) conjecture\(N\)-freebalanced pair

Mathematics Subject Classification ID

Partial orders, general (06A06) Total orders (06A05)

Cited In (12)

• Greedy balanced pairs in \(N\)-free ordered sets
• A family of partially ordered sets with small balance constant
• Finding large 3-free sets. I. The small \(n\) case
• Linear extensions of N-free orders.
• Sorting probability for large Young diagrams
• Improving the \(\frac{1}{3}\)-\(\frac{2}{3}\) conjecture for width two posets
• The 1/3-2/3 conjecture for ordered sets whose cover graph is a forest
• On the \(1/3-2/3\) conjecture
• On the fixed point property for \((3 + 1)\)-free ordered sets
• Semiorders and the 1/3-2/3 conjecture
• Title not available (Why is that?)
• On the dual König property of the order-interval hypergraph of two classes of \(N\)-free posets

This page was built for publication: The \(1/3\)-\(2/3\) conjecture for \(N\)-free ordered sets

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