The \(1/3\)-\(2/3\) conjecture for \(N\)-free ordered sets (Q426908)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The \(1/3\)-\(2/3\) conjecture for \(N\)-free ordered sets |
scientific article |
Statements
The \(1/3\)-\(2/3\) conjecture for \(N\)-free ordered sets (English)
0 references
12 June 2012
0 references
Let \(P = (V,\preceq)\) be a poset (that is, a partially ordered set). An ordered pair \((x,y)\) of elements in \(V\) is a \textit{balanced pair} of \(P\) if the proportion of linear extensions of \(P\) in which \(x\prec y\) is in the real interval \([1/3, 2/3]\). Call an ordered 4-tuple \((a,b,c,d)\) of distinct elements of \(V\) an N in \(P\) if the comparabilities among these four elements are exactly \(a\prec b\), \(c\prec b\), and \(c\prec d\) (so the sub-poset induced by \(a,b,c,d\) looks like a capital ``N''). The poset \(P\) is \textit{N-free} if it does not contain an N as an induced poset. The main result of the paper is that every finite N-free poset that is not totally ordered has a balanced pair.
0 references
ordered set
0 references
linear extension
0 references
\(N\)-free
0 references
balanced pair
0 references
\(1/3\)-\(2/3\) conjecture
0 references