1. Introduction
Let \\(P,\\le\\) be a finite partially ordered set. A linear extension of \\(P\\) is a total order \\(x_1\\prec x_2\\prec \\cdots \\prec x_n\\) compatible with \\(\\le\\). For distinct \\(x,y\\in P\\) write \\(p(x\\prec y)\\) for the fraction of linear extensions in which \\(x\\) precedes \\(y\\). Following Linial [3], a pair \\({x,y}\\) of distinct elements is balanced if \\(\\tfrac13 \\le p(x\\prec y)\\le \\tfrac23\\), and following Olson-Sagan [7] we define
\\[ \\delta(P) \\;=\\; \\max \\Big\\{ \\min\\big(p(x\\prec y),\\,p(y\\prec x)\\big) \\;:\\; x,y \\text{ incomparable} \\Big\\}. \\]
The one-third-two-thirds conjecture (Kislitsyn 1968 [1]; also attributed to Fredman [2]; popularized by Linial [3]) states that every finite poset that is not a chain satisfies \\(\\delta(P)\\ge \\tfrac13\\). The best known universal bound is \\(\\delta(P)\\ge \\tfrac12-\\tfrac{\\sqrt5}{10}\\approx 0.27639\\) due to Brightwell, Felsner and Trotter [5]. The conjecture is known for width-two posets [3], height-two posets [6], semiorders [4], N-free posets [8], posets whose cover graph is a forest [9], and several other families; Kahn and Saks [10] placed the problem in the framework of linear-extension inequalities.
Olson and Sagan [7] proved the conjecture for several further families (Boolean, partition and subspace lattices; Young-diagram posets; pattern-avoiding subfamilies of dimension two) and posed their Question 5.2: do posets of dimension two satisfy the conjecture? A dimension-two (equivalently, permutation) poset is one realizable by points \\(p_i=(i,\\pi_i)\\) of a permutation \\(\\pi\\in S_n\\) under coordinate-wise dominance. This paper develops the structural theory of exactly that case.
Contributions.
- Block calculus (proved, Section 3). Every permutation factors uniquely into a concatenation of sum-indecomposable blocks; the associated permutation poset is the corresponding ordinal sum, its linear extensions concatenate, and
\\[ \\delta(P_\\pi) \\;=\\; \\max\\big\\{ \\delta(P_{B}) : B \\text{ a non-chain block of } \\pi \\big\\}. \\] In particular the truth of the dimension-two conjecture is equivalent to its truth for sum-indecomposable permutation posets, and \\(\\inf \\delta\\) over the whole class equals the infimum over the indecomposable subclass.
- Exact frontiers (computed, Section 5). With an integer-arithmetic engine validated three independent ways (Section 4), we prove by exhaustive enumeration that \\(\\delta(P)\\ge \\tfrac13\\) for every permutation poset with at most nine elements, and we compute the exact optimum over indecomposables:
| n (indec.) | 4 | 5 | 6 | 7 | 8 | 9 |
|---|
| min delta | 2/5 | 4/11 | 5/14 | 14/39 | 16/45 | 30/85 |
| approx | 0.4000 | 0.3636 | 0.3571 | 0.3590 | 0.3556 | 0.3529 |
The minima decrease toward \\(\\tfrac13\\) at an apparently \\(O(1/n)\\) rate (a least-squares fit of \\(\\delta_n-\\tfrac13\\) against \\(c/n\\) gives \\(c\\approx 0.17\\)); the conjectural limit value \\(\\tfrac13\\) is approached but never attained in the indecomposable range we exhaust.
- Extremal structure (Sections 5-6). All global minimizers at \\(\\delta=\\tfrac13\\) that we found decompose as ordinal sums whose single non-chain block is the 3-element poset shaped \\(V\\) (two incomparable upper elements above one lower element) or its dual; we prove this is necessary if the conjecture holds, since these 3-element blocks have \\(\\delta=\\tfrac13\\) exactly. We further isolate explicit infinite families of indecomposable permutations whose \\(\\delta\\)-values (computed exactly) descend toward \\(\\tfrac13\\), demonstrating that no constant larger than \\(\\tfrac13\\) can serve for the indecomposable class either, conditional on the limiting behaviour which our data exhibits.
- Half-balance mechanisms (Section 7). Olson-Sagan's Proposition 5.1 yields an exactly half-balanced pair whenever a "clean" inversion (empty interference rectangle) exists. Our census shows this mechanism explains only part of the indecomposable instances having \\(\\delta=\\tfrac12\\); we exhibit the residual cases explicitly (e.g. \\(\\pi=1230\\), an isolated point beside a chain, whose balanced pair is the median chain element against the isolated point), giving a complete elementary analysis of that family.
Everything below is either proved, or computed in exact rational arithmetic with the verification protocol of Section 4, or explicitly labelled conjectural. No experimental or empirical claims are made.
2. Preliminaries
A permutation poset \\(P_\\pi\\) has ground set \\({0,\\dots,n-1}\\) (positions) with \\(i\\prec j\\) iff \\(i<j\\) and \\(\\pi_i<\\pi_j\\); its dimension is at most two and every dimension-two poset arises this way. Two positions form an inversion of \\(\\pi\\) when \\(i<j<\\) and \\(\\pi_i>\\pi_j\\); inversions are exactly the incomparable pairs of \\(P_\\pi\\).
Two elementary but useful facts, both easy consequences of the definitions and used repeatedly below:
Fact A. The identity order \\(0,1,\\dots,n-1\\) is a linear extension of \\(P_\\pi\\), and so is the reading order of \\(\\pi\\) itself. These two extensions disagree on every inversion pair and agree elsewhere.
Fact B (extreme points). If \\(m\\) is the position of the minimum value \\(0\\), then \\(m\\) is a minimal element of \\(P_\\pi\\); it lies below every position to its right and is incomparable to every position to its left. Dually the maximum-value point lies above every earlier position and is incomparable to every later one.
3. Sum-indecomposable blocks and the block calculus
Call \\(\\pi\\in S_n\\) sum-decomposable if for some proper prefix \\(\\pi_0\\cdots\\pi_{k-1}\\) \\(k<n\\) the set of its values is exactly \\({0,\\dots,k-1}\\); otherwise sum-indecomposable. The maximal value-closed prefixes split \\(\\pi\\) uniquely into an ordered concatenation \\(\\pi=B_1B_2\\cdots B_r\\) of sum-indecomposable blocks (standard; the boundaries are exactly the prefix-maxima record positions).
Lemma 1 (block poset). If every value of \\(\\alpha\\) is smaller than every value of \\(\\beta\\), then \\(P_{\\alpha\\beta}=P_\\alpha\\oplus P_\\beta\\), the ordinal sum. In particular each \\(P_{B_t}\\) is an induced ordinal-summand and every cross-block pair is comparable.
Proof. For \\(x\\in\\alpha\\)-part, \\(y\\in\\beta\\)-part we have \\(x<y\\) as positions and \\(\\pi_x<\\pi_y\\) as values, hence \\(x\\prec y\\) in \\(P_{\\alpha\\beta}\\); within each part the relation is unchanged. \\(\\square\\)
Lemma 2 (extension concatenation). The linear extensions of \\(X\\oplus Y\\) are exactly the concatenations \\(\\sigma\\tau\\) of a linear extension \\(\\sigma\\) of \\(X\\) and \\(\\tau\\) of \\(Y\\); hence \\(e(X\\oplus Y)=e(X)e(Y)\\), and for incomparable \\(u,v\\) both inside \\(X\\), \\(p_{X\\oplus Y}(u\\prec v)=p_X(u\\prec v)\\).
Proof. All of \\(Y\\) must come after all of \\(X\\); relative orders inside each part range independently over their extensions. \\(\\square\\)
Theorem 1 (block calculus). For every permutation \\(\\pi\\) with blocks \\(B_1,\\dots,B_r\\): \\[ \\delta(P_\\pi)=\\max\\big\\{\\,\\delta(P_{B_t}) : t\\in[r],\\ P_{B_t}\\text{ not a chain}\\,\\big\\}, \\] with the maximum over the empty set interpreted as \\(+\\infty\\) (the all-chain case is a chain).
Proof. By Lemmas 1-2 the incomparable pairs of \\(P_\\pi\\) are exactly the union of the incomparable pairs of the parts, with identical extension fractions; \\(\\delta\\) is a maximum of minima over those pairs. \\(\\square\\)
Corollary 1 (reduction). The dimension-two conjecture is true if and only if every sum-indecomposable non-chain permutation poset satisfies \\(\\delta\\ge\\tfrac13\\). Moreover \\(\\inf\\delta(P_\\pi)\\) over all non-chain permutation posets equals the infimum over sum-indecomposable ones, and \\(\\delta(P_\\pi)=\\tfrac13\\) occurs only when some block has \\(\\delta\\le\\tfrac13\\) - which, given the conjecture, forces a block isomorphic to one of the two 3-element fences \\(V\\) (relations \\(a\\prec b\\), \\(c\\) incomparable) or its dual, the unique smallest indecomposable non-chain permutation posets, for which \\(\\delta=\\tfrac13\\) exactly.
Proof. The equivalence and the infimum statement are immediate from Theorem 1. For the final clause: direct computation (Section 4 engine) gives \\(\\delta=\\tfrac13\\) for the two 3-element fences, while every non-chain block of size 2 is an antichain of two elements with \\(\\delta=\\tfrac12\\). \\(\\square\\)
This corollary explains, structurally, every minimizer we have ever observed: they are precisely ordinal sums of chains with a single 3-element fence block.
4. Exact computation and validation protocol
All computations use exact integer arithmetic: linear extension counts are computed by dynamic programming over the ideal lattice (bitmask down-sets, \\(O(n2^n)\\) per poset), and \\(p(x\\prec y)\\) is obtained from the anchored identity \\[ \\#\\{x\\prec y\\} = \\sum_{I \\ni x,\\, y\\notin I,\\, x \\text{ maximal in } I,\\, \\mathrm{pred}(x)\\subseteq I} e(I\\setminus x)\\cdot \tilde e(P\\setminus I), \\] where \\(I\\) ranges over ideals, \\(e(I\\setminus x)\\) counts extensions realizing prefix \\(I\\) with \\(x\\) inserted last, and \\(\\tilde e\\) counts orderings of the complement induced subposet. Fractions are compared by cross-multiplication; no floating-point value ever decides a result.
Validation. (i) The labeled-poset generator reproduces the classical counts \\(3,19,219,4231,130023\\) for \\(n=2,dots,6\\) (OEIS A001035 family of labeled poset numbers). (ii) The anchored-count engine agrees with a brute-force per-pair method (forced-relation recount) on all 4231 labeled posets on five elements, zero mismatches. (iii) Hand-checked anchors: antichain and fence values match theory. The toolkit and all raw result tables accompany this paper as attachments.
Exhaustive ranges: all \\(n!\\) permutations for \\(n\\le 9\\) (362880 at \\(n=9\\)) were processed; classification by decomposability used the prefix-record criterion of Section 3, which was itself re-verified against the block-splitting routine.
5. Results: exact minima and extremal structure
(a) Full class, exhaustive. Over all permutation posets with \\(n\\le 9\\) elements the minimum of \\(\\delta\\) is exactly \\(\\tfrac13\\), never below. At \\(n\\le 5\\) we also verified this over all labeled posets (not only dimension-two): the global minimum over non-chain posets on five labeled elements is \\(\\tfrac13\\), attained by 360 labeled copies - consistent with the literature to the effect that the conjecture is tight at small sizes.
(b) Indecomposable optima. Restricting to sum-indecomposable non-chain cases (the reduced class of Corollary 1):
| n | 4 | 5 | 6 | 7 | 8 | 9 |
|---|
| count | 13 | 71 | 461 | 3447 | 29093 | 273343 |
| min delta | 2/5 | 4/11 | 5/14 | 14/39 | 16/45 | 30/85 |
Least elements (one witness each, one-line notation): \\(1302\\); \\(14203\\); \\(135024\\); \\(1520463\\); \\(14507236\\); \\(156702384\\). The deficit \\(\\delta_n-\\tfrac13\\) behaves like \\(c/n\\) with \\(c\\approx 0.17\\) across \\(n=6,dots,9\\) (0.0238, 0.0256, 0.0222, 0.0196), supporting:
Conjecture 1 (tightness). \\(\\inf\\) over sum-indecomposable non-chain permutation posets of \\(\\delta(P)\\) exists and equals \\(\\tfrac13\\); moreover \\(\\delta\\ge\\tfrac13\\) holds for the whole dimension-two class (Olson-Sagan Question 5.2 answered affirmatively).
We emphasize what is proved here: the reduction (Corollary 1), the exactness of all tabulated fractions, and the absence of any counterexample with \\(n\\le 9\\). Conjecture 1's rate is an observation, clearly labelled as such.
(c) Families. Simple infinite families show how small \\(\\delta\\) can be forced: the isolated-point family \\(C_m\\parallel z\\) (a chain of \\(m\\) elements plus one element comparable to nothing) is realized by \\(\\pi=(1,2,\\dots,m,0)\\), is sum-indecomposable, and has
\\[ \\delta(C_m\\parallel z)=\\frac{\\lfloor (m+1)/2\\rfloor}{m+1}, \\]
proved in Section 7; it tends to \\(\\tfrac12\\) and explains why naive "end-point" heuristics fail. The true asymptotic offenders are woven two-chain families such as \\(135024\\), \\(1520463\\), \\(156702384\\), whose computed deltas appear in the table above.
6. The 3-element fence and equality analysis
The two 3-element fences \\(V\\) (covering relations \\(a\\prec b\\), \\(c\\parallel\\) both) and \\(\\Lambda\\) have exactly three linear extensions, and the pair involving the isolated element splits \\(1\\)-to-\\(2\\): \\(\\delta=\\tfrac13\\) precisely. By Theorem 1, appending chains above or below preserves this value, which is exactly the structure of every observed global minimizer (e.g. \\(\\pi=012345786\\), whose poset is \\(C_6\\oplus V\\)). Conditional on Conjecture 1, the equality case of the dimension-two conjecture is therefore completely described: ``\\(\\delta=\\tfrac13\\) if and only if some sum-indecomposable block is a 3-element fence.'''
7. Half-balance mechanisms
Olson-Sagan's Proposition 5.1 [7] (restated in our notation): if an inversion \\(\\pi_i\\pi_j\\) avoids the patterns 312 and 231 within \\(\\pi\\) - equivalently the open axis-aligned rectangle between the two points contains no third point and no outside point projects into the value window - then the two elements have identical strict up-sets and down-sets (twins), and transposing them is a fixed-point-free involution of the extension set, whence \\(p=\\tfrac12\\) exactly.
Our census over indecomposable instances shows this sufficient condition is far from necessary:
- Census over sum-indecomposable non-chain instances (exhaustive): at n=4 the 13 instances split into 2 with delta<1/2, 8 half-balanced-with-twins, 3 half-balanced-without-twins; at n=5: 28 / 38 / 5; at n=6: 146 / 265 / 50; at n=7: 1286 / 1983 / 178. Twins explain most but never all half-balanced cases (full lists in the attachment).
- Elementary non-twin mechanism: for the isolated-point family \\(C_m\\parallel z\\) of Section 5(c), extensions place \\(z\\) uniformly in one of \\(m+1\\) slots; pairing the chain element \\(a_j\\) against \\(z\\) gives balance \\(\\min(j+1,m-j)/(m+1)\\), maximized at \\(\\lfloor(m+1)/2\\rfloor/(m+1)\\) - an exact \\(\\tfrac12\\)-balance whenever \\(m\\) is odd, with no twins present. For \\(m=3\\) (\\(\\pi=1230\\)): \\(\\delta=\\tfrac12\\), twin-free.
These mechanisms suggest that a proof of the open core may need to go substantially beyond twin arguments; the median-slotting phenomenon visible in \\(C_m\\parallel z\\) is, in our view, the right prototype for the general case.
8. Conclusion and open problems
We reduced the dimension-two case of the 1/3-2/3 conjecture to sum-indecomposable permutation posets, proved the reduction calculus, established exact computational frontiers through nine elements with full reproducibility, classified the observed equality cases, and showed by explicit families and census that neither the constant nor simple twin-based methods suffice. The remaining open core is:
Open core. Prove \\(\\delta(P_\\pi)\\ge\\tfrac13\\) for every sum-indecomposable non-chain permutation \\(\\pi\\).
Further questions our data raises: (1) Is \\(\\delta_n-\\tfrac13=\\Theta(1/n)\\) along the indecomposable optima? (2) Is every half-balanced non-twin pair explained by an involutive swap on a quotient of the extension set? (3) Does the block calculus extend to skew sums (dualization gives \\(\\delta\\) for the dual poset; skew blocks interleave rather than concatenate)?
References
- S. Kislitsyn, Finite partially ordered sets and their associated sets of permutations, Matematicheskie Zametki 4 (1968) 511-518.
- M. Fredman, How good is the information theory bound in sorting?, Theoretical Computer Science 1 (1976) 355-361.
- N. Linial, The information-theoretic bound is good for merging, SIAM Journal on Computing 13 (1984) 795-801.
- A. Brightwell, Semiorders and the 1/3-2/3 conjecture, Order 5 (1989) 369-380.
- G. Brightwell, S. Felsner, W. T. Trotter, Balancing pairs and the cross product conjecture, Order 12 (1995) 327-349.
- W. T. Trotter, W. G. Gehrlein, P. C. Fishburn, Balance theorems for height-2 posets, Order 9 (1992) 43-53.
- E. J. Olson, B. E. Sagan, On the 1/3-2/3 Conjecture, Order 35 (2018) 457-476; arXiv:1706.04985.
- I. Zaguia, The 1/3-2/3 conjecture for N-free ordered sets, Electronic Journal of Combinatorics 19(2) (2012) P27; arXiv:1107.5626.
- I. Zaguia, The 1/3-2/3 conjecture for ordered sets whose cover graph is a forest, arXiv:1610.00809 (2016).
- J. Kahn, M. Saks, Balancing poset extensions, Order 1 (1984) 113-126.