Improving the $$\frac{1}{3} - \frac{2}{3}$$ Conjecture for width Two Posets
- PDF / 518,076 Bytes
- 28 Pages / 442.205 x 665.008 pts Page_size
- 50 Downloads / 183 Views
Bolyai Society – Springer-Verlag
Combinatorica 28pp. DOI: 10.1007/s00493-020-4091-3
IMPROVING THE 13 – 23 CONJECTURE FOR WIDTH TWO POSETS ASHWIN SAH Received November 11, 2018 Revised March 25, 2020 Extending results of Linial (1984) and Aigner (1985), we prove a uniform lower bound on the balance constant of a poset P of width 2. This constant is defined as δ(P ) = max(x,y)∈P 2 min{P(x ≺ y), P(y ≺ x)}, where P(x ≺ y) is the probability x is less than y in a uniformly random linear extension of P . In particular, we show that if P is a width 2 poset that cannot be formed from the singleton poset and the three element poset with one relation using the operation of direct sum, then √ −3 + 5 17 δ(P ) ≥ ≈ 0.33876 . . . . 52 This partially answers a question of Brightwell (1999); a full resolution would require a proof of the 31 – 23 Conjecture that if P is not totally ordered, then δ(P ) ≥ 31 . Furthermore, we construct a sequence of posets Tn of width 2 with δ(Tn ) → β ≈ 0.348843 . . ., giving an improvement over a construction of Chen (2017) and over the finite posets found by Peczarski (2017). Numerical work on small posets by Peczarski suggests the constant β may be optimal.
1. Introduction Definition 1.1. Given a fixed, underlying poset (P, ≤), P(x ≺ y) is the probability that x precedes y in a uniformly random linear extension of P . We define P(x ≺ x) = 0. A conjecture dating back to 1968 states that in any finite 1 2 partial order not a chain, there is a pair (x, y) such that P(x ≺ y) ∈ 3 , 3 . Kislitsyn [13], Fredman [9], and Linial [14] independently made this so-called 13 – 23 Mathematics Subject Classification (2010): 06A07, 05A20, 05D99
2
ASHWIN SAH
Conjecture. Each had in mind an application to sorting theory. In particular, this conjecture implies that the number of comparisons needed to fully sort elements that are already known to be in the partial order P is at most (1+o(1)) log 3 e(P ), within a constant factor of the trivial information2 theoretic lower bound log2 e(P ). Here e(P ) is the number of linear extensions of P . Definition 1.2. The balance constant of poset P is δ(P ) = max min{P(x ≺ y), P(y ≺ x)}. (x,y)∈P 2
We can thus restate the 13 – 32 Conjecture as follows. Conjecture 1.3. If P is a finite poset that is not totally ordered, then δ(P ) ≥ 31 . Brightwell [3] deemed it “one of the major open problems in the combinatorial theory of partial orders.” This conjecture is known to be true for certain classes of posets: width 2 by Linial [14], height 2 by Trotter, Gehrlein, and Fishburn [18], 6-thin by Peczarski [16], semiorders by Brightwell [4], N -free posets by Zaguia [19], and posets whose Hasse diagram is a forest by Zaguia [20]. We can ask how the balance constant interacts with the fundamental operations of disjoint union and direct sum. (Direct sum will be important in characterizing equality cases.) It is clear that if ⊕ denotes direct sum of posets and t disjoint union of posets, then δ(P ⊕ Q) = max{δ(P ), δ(Q)}, δ(P t Q) ≥ max{δ(P ), δ(Q)}. We more formally define P ⊕ Q
Data Loading...
