Local comparison counting for linear extensions and a bounded-range balance refinement
We determine the smallest positive probability of a specified order of three vertices in a uniformly random linear extension of a finite poset with maximum incomparability degree at most D. Writing c_j = binom(2j, j), its reciprocal is M_D = c_D/2 + ((⌊D²/4⌋ + D)/(2D)) c_⌊D/2⌋ c_⌈D/2⌉ (D ≥ 2). Two-chain bridge posets attain this bound. In particular M_D ~ 4^D/(4π). The proof first conditions on comparisons that remain unresolved after the desired order is imposed. This reduces the extremal problem to an event realized by a single extension. A structural reduction then leaves two chains and a middle vertex; an exact finite difference locates the extremal insertion threshold. For four marked vertices the exact reciprocal is binom(2D, D)². More generally, writing B_D = binom(2D, D), the exact reciprocal is B_D^r for 2r marked vertices and M_D B_D^(r−1) for 2r+1 ≥ 3 marked vertices, for every D ≥ 2. For even mark counts we characterize equality and determine the second smallest positive probability. Excluding saturated two-chain incomparability components gives a further exact formula for every mark count. Thus the optimal exponential denominator rate for fixed m is 4^(D⌊m/2⌋). Combining the sharp triple estimate with the current quantitative balance analysis gives a bounded-range increment asymptotic to (4π/(5+3√5)) 4^(−D) above the classical BFT constant for posets with bounded incomparability degree. This replaces the increment (D+1)^(−3(D+1))/12 of Aires, Chan, Pak and Panova, which they sharpen to (D+1)^(−3(D+1))/(5+3√5), by one of order 4^(−D); for D ≤ 6 the balance bound 1/3 is already known, so the gain applies from D = 7 onward. The exact marked-order floors sharpen their bound (D+1)^(−m(D+1)) for events specified by comparisons among m elements.
Authors
- Scott Schubr (ORCID: https://orcid.org/0009-0009-7357-4439)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-20
- DOI
- https://doi.org/10.5281/zenodo.24408119
- Primary Topic
- Advanced Combinatorial Mathematics
- Type
- preprint