Poset balance constant improves after 30 years breaking theoretical barrier
Breaking the Infinite Barrier in the $\frac{1}{3}$--$\frac{2}{3}$ Conjecture
Discrete Mathematics
Summary
There is a longstanding math puzzle about sorting elements and how often certain pairs appear in order. The authors improved a known limit on how balanced this ordering can be, making a small but significant advance. This is the first progress in over three decades on this particular sorting problem. Their result shows a bit more equality in how elements can be arranged than previously known.
What this means in practice
- •For sorting algorithm designers: Use improved understanding of element order distribution bounds to refine probabilistic sorting guarantees.
- •For complexity theorists: Incorporate tighter order bounds into complexity analyses of algorithms involving partial order constraints.
A theory result. No direct application yet.
Authors
Max Aires, Swee Hong Chan, Igor Pak, Greta Panova
Abstract
The balance constant is a poset parameter measuring how well random linear extensions can be split according to their relative order on two elements. We give an $\varepsilon$-improvement for the balance constant over the bound by Brightwell, Felsner and Trotter (1995), for some small $\varepsilon>0$. This is the first general result towards the $\frac{1}{3}$--$\frac{2}{3}$ conjecture in over 30 years.