Local comparison counting for linear extensions and a bounded-range balance refinement
Loading original first page…
Abstract
For uniform linear extensions of a finite poset with maximum incomparability degree at most D, we give a local stable-partition estimate and track the incomparabilities removed by conditioning. Every consistent specified order of three marked vertices has probability at least F_D^(-1), where F_D=binom(D+⌊ D/2⌋, ⌊ D/2⌋) binom(2D-⌊ D/2⌋, D). This denominator has order Θ((27/4)^D/D). Substitution into the finite-boundary argument of Aires–Chan–Pak–Panova gives a sharper explicit bounded-range balance estimate. A complementary two-chain construction shows that a triple-order estimate cannot universally use even a constant multiple of the sharp pair probability: its rare order has reciprocal probability asymptotic to 16^k/(4π) at range D=2k. These are quantitative counting refinements and a method limitation.
Read the full paper in the original PDF.
Edition files
- paper.pdf83.7 KiB · pdf
SHA-256
7b32b4ed5f5e0dc029072dd062d37c56f88ba0f388a0ad2cf52935bb6a53a7d8 - Revised_publication_package.zip97.6 KiB · package
SHA-256
6b5629c177bb18c5f7db1961b397c2591ae25ad0961525953426988244f0ef89
Available editions
Research details
- Subjects
- Mathematics · Combinatorics and Graph Theory
- Keywords
- partially ordered sets, linear extensions, balance, incomparability degree, local comparison counting
- Manuscript date
- 2026-10-20
- Reader reuse
- No additional permission granted
Scope
A conditioned local stable-partition counting estimate and explicit three-vertex order bound yield the stated bounded-range balance refinement, with a two-chain obstruction to replacing triple-order probabilities by a universal multiple of the sharp pair probability.
Disclosures
AI tools assisted proof exploration, literature review, verification-code development and manuscript preparation. Independent AI checks are not external human peer review.
Reproduction
The paper has 7 pages. The editable-source archive contains 7 files. Compile source/main.tex. Standard-library reproducibility/verify.py provides quick checks through five vertices or --full checks through six vertices, with exact stored result comparisons.