The one-third–two-thirds conjecture for sorting probability
The one-third–two-thirds conjecture for sorting probability
Let be a finite poset, and let denote its sorting probability. A poset is a chain if every pair of elements is comparable.
The one-third–two-thirds conjecture. For every finite poset that is not a chain, we have
This conjecture is known for several classes of posets, including Young diagrams and skew Young diagrams, but remains open for general finite posets. The bound is tight for the three-element poset consisting of a two-element chain and an isolated element.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Swee Hong Chan, Igor Pak and Greta Panova, “Sorting probability for large Young diagrams”, arXiv:2005.08390 (2021).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.