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

At least 5 years old · documented by

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.

References

Primary source

Swee Hong Chan, Igor Pak and Greta Panova, “Sorting probability for large Young diagrams”, arXiv:2005.08390 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.