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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Local comparison counting for linear extensions and a bounded-range balance refinement

Scott Schubr
1 links
Zenodo (CERN European Organization for Nuclear Research)
Advanced Combinatorial Mathematics
preprint

Local comparison counting for linear extensions and a bounded-range balance refinement

Scott Schubr
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Advanced Combinatorial Mathematics
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon