The 1/3–2/3 Conjecture

An interesting unsolved conjecture in order theory

Resources to learn more and other interesting notes:
_____________________

Poset resources:
_____________________

The 1/3-2/3 conjecture:

An earlier (and weaker) result with an easier proof to follow:

More about the result:
_____________________

Corrections:
The conjecture should have said for any partial order that is not a total order. That is, it cannot already be a complete ranking.

[joshuazelinsky]

This is an excellent summary of the 1/3 -2/3 conjecture.

Three related things worth noting: First, with probability 1, an ordering obeys the 1/3-2/3 conjecture. That is, if we look at the proportion of n-element partial orders that obey the 1/3–2/3 conjecture, that fraction goes to 1 as n goes to infinity.

Second, the 27% you quote is an approximation for the actual number in the paper which proved that result by Brightwell, Felsner, and Trotter, where they showed the result for the number 1/2 − sqrt(5)/10 which is about 0.27639... Third, they were able to show that there are some infinite partial orders where it still makes sense to ask about these probabilities, and for those, the bound they got is best possible. When I first saw the BFT result, my naive guess was there should be some way to extend there infinite examples to the finite example, and I don't understand well why there does not seem to be anything of that sort.

[Qermaq]

Let's start a punset by ranking how good the dad jokes in this video were.

[shaharjoselevich]

One third
two thirds
red third
blue third

[jyrinx]

In case this was bothering anyone else: A poset _can_ happen to be totally ordered (a straight line) already, in which case every sorting probability is either 0 or 1 (since every comparison is already determined). In its full form, the conjecture stipulates that the poset isn't totally ordered.

[mcmagic]

I personally like apples over oranges, oranges over bananas, and bananas over apples

[lexinwonderland]

"I like apples more than I like bananas. But, I'm not going to tell you how I feel about oranges, *you pervert*." i had to stop the video from laughing so hard at that non sequitur right out of the gate, great stuff m8, it's always a delight to see you post a video!!

[pe]

i'm so used to 30 minute plus videos i forgot how nice it is to have something concice, thank you

[hindigente]

What a fruitful YouTube recommendation!

[andrewharrison]

I hadn't realised this branch of mathematics existed. It obviously (with hindsight) is a down in the weeds part of sorting.
For sorting you generally want each comparison to halve the number of possibilities left but in practice accept much less even results so this conjecture provides a target for the sorting algorithm (in practice simplicity of implementation is also a concern*).

* as a programmer debugging an optimal and therefore complex algorithm does not appeal

[aviasegel]

Math and puns, all you need for a balanced YouTube diet

[maxwchase]

"pair down"... The subs chose violence.

[soupy]

I've never touched order theory but I might do some reading up after this, fun video

[katherinefirsdon]

those two fruit puns at the end. oh man. worth a watch for those alone.

[mtirado]

Such a nice and clear explanation of posets!

[AdamPickarski]

Nice video! I wonder if you can make a follow up about the Bradley Terry Model!

[yb]

enjoyable video and a cool conjecture
thanks

[davejacob]

The graph in your thumbnail and at around 1:48 confused me: Is this a partially ordered graph where it is unclear whether 4 is valued higher than 5 or the other way around? Is the linear graph on the right supposed to be a counterexample where we know exactly that 4 is valued higher than 5? if so, it would have been much less confusing if the right graph had other items (or simply another number or items) within it. Shown like this it seems as if the right graph is supposed to be some kind of "translation" of the left graph, even though, again: it is unclear whether 4 or 5 should be regarded as "higher".

[JoeDeglman]

Your premise that there must be a solution is contradicted by the requirements 1:35 that the ordering must be transitive, or that one apple, orange, or banana outranks the others.

[RUDRARAKESHKUMARGOHIL]

you nailed it ! a nice application of order theory and probability where we can find a order of 2 any element whose probability in partial order sets linear extensions(i.e just all the possible comparison of available partial info. of order or in other words partial order) is between 1/3 and 2/3 and more concretely with proof between 27 % and 73 % so finding this comparison can at least cut down 27 % of linear extension so rapidly decreasing the no. of comparison actually needed to perform just 1 is enough...i read your its use example in a game contest do you have any application in physics point of view ?

[ForsakenDAemon]

Is there a limit on the number of ordered pairs in the poset? Under the definitions I’ve used before, a strict loset is a poset (since a total order is also a partial order), but the probability there is either 0 or 1 for every pair.