The one-third–two-thirds conjecture for sorting probability

From papers

Let P=(X,)P=(X,\prec) be a finite poset, and let δ(P)\delta(P) 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 P=(X,)P=(X,\prec) that is not a chain, we have

δ(P)13.\delta(P)\le \frac13.

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

No solutions have been posted yet.