How many ways to sort it

An order is a partial description. It says $a$ comes before $b$, and $c$ before $d$, and leaves everything else open. The natural measure of how much it leaves open is the number of complete orderings consistent with it.

A linear extension is such an ordering: a listing of the elements respecting every relation the order states. A total order has one; an order with no relations at all has $n!$; everything else is in between, and the number is the size of what is still undecided.

What the number measures #

Three readings, and each is used somewhere.

As ignorance. Suppose the elements have a true total order and the partial one is what is known so far. Then the linear extensions are exactly the possibilities still open, and their count is the size of the search space. Sorting is the process of shrinking it to one.

As volume. Represent each linear extension as a region of the unit cube — the set of points whose coordinates are ordered that way — and the regions are congruent simplices of volume $1/n!$. So the count divided by $n!$ is the probability that $n$ independent uniform numbers happen to be ordered consistently with the given order, which turns a counting problem into a geometry one. That reading is what the random-walk approximation exploits: sampling a linear extension becomes sampling a point of the cube, and the geometry of the region is what makes the walk mix quickly.

As a measure of order. An order with many relations has few extensions, and one with few relations has many. The count runs from $1$ to $n!$ and interpolates between “everything is decided” and “nothing is”.

The third reading has a quantitative form worth keeping. The logarithm of the count is the number of bits still missing — the entropy of the unknown total order — so a comparison that halves the count buys exactly one bit. That is the connection to sorting, and it is why the conjecture below is a statement about information rather than about orders.

The figure computes it twice, deliberately. Once by enumerating the extensions one at a time, and once by a recursion over the set of elements already placed — which is a different algorithm with a different cost — and the two are asserted equal.

Counting is hard #

The recursion above visits every down-set of the order, of which there can be exponentially many, and no better method is known. That is not for want of trying.

Counting linear extensions is #P-complete, proved by Brightwell and Winkler in 1991. That is the counting analogue of NP-completeness: an efficient algorithm would give efficient algorithms for counting the solutions of every problem in a very large class, which nobody expects to exist.

The contrast with the neighbouring questions is stark and worth stating.

• Finding one linear extension is easy: a topological sort, linear time — the same walk that orders the tasks of a dependency graph.
• Finding the largest antichain is easy: a matching, by Dilworth’s theorem.
• Finding the longest chain is easy: a shortest-path computation.
• Finding the number of down-sets — which is a different count of the same order — is also #P-complete.
• Counting the linear extensions is as hard as counting gets.

That pattern — decision easy, counting hard — recurs throughout the subject, and it is the reason approximate counting has a literature of its own. There is a randomised approximation scheme for this one, by sampling extensions with a random walk, and it is one of the successes of that method. The walk swaps two adjacent elements of a current extension when the swap keeps it legal; it mixes rapidly, and the count follows from how often the walk visits particular states. That is a genuine algorithm and it is worth contrasting with what is not available: no formula, no recursion smaller than exponential, and no way to get the exact number for an order of a few hundred elements.

The pair that splits them evenly #

The second column of the figure is the interesting one, and it is where an open problem lives.

For an incomparable pair $x, y$, let $p(x,y)$ be the fraction of linear extensions putting $x$ before $y$. It is between 0 and 1, and it is exactly 0 or 1 only when the pair is comparable — which they are not, by assumption.

The 1/3–2/3 conjecture. Every finite order that is not total has an incomparable pair with $\tfrac13 \le p(x,y) \le \tfrac23$.

Read it as a statement about sorting. Comparing $x$ and $y$ splits the remaining possibilities into two groups of sizes $p$ and $1-p$; whichever answer comes back, at least a $\tfrac13$ fraction is eliminated. So the conjecture says a good comparison is always available, and therefore that any order can be sorted in $O(\log e(P))$ comparisons where $e(P)$ is the number of extensions — which is the information-theoretic minimum up to a constant.

It has been open since Kislitsyn posed it in 1968. The best general bound is that some pair has $p$ between about $0.2764$ and $0.7236$ — the golden-ratio-related constants $(3-\sqrt5)/2$ and its complement — proved by Brightwell, Felsner and Trotter in 1995 and not improved since.

Why it is hard to prove #

A conjecture this old with a statement this short has usually had every easy idea tried on it, and the record of what fails is informative.

The conjecture looks like the kind of statement an averaging argument should settle, and every obvious averaging argument fails.

Sum $p(x,y)$ over all incomparable pairs and the total is determined by the number of such pairs — the sum of $p(x,y)$ and $p(y,x)$ is one for each pair — so the average is exactly one half. That establishes nothing: an average of one half is consistent with every pair being at $0.1$ or $0.9$.

The difficulty is that the balanced pair might have to be found rather than shown to exist by counting. Attempts to identify it structurally — take the pair whose $p$ is closest to a half, or the pair in the middle of the longest chain — fail on constructed examples, and the known bound comes from a correlation inequality rather than from a construction.

There is one class where it is settled and the proof is a good illustration of what would be needed in general. For orders of width two — those cuttable into two chains — the conjecture holds, and the argument is essentially about a lattice path staying near a diagonal. Getting from width two to width three has not been done. Width is exactly the quantity Dilworth’s theorem computes, so the frontier of the conjecture is stated in terms of an invariant that is easy to calculate and useless for the proof — which is a common and frustrating shape.

There is one more failed idea worth recording, because it is the one most people try second. Take the element in the middle of a longest chain and pair it with something incomparable: the hope is that a long chain forces balance somewhere near its middle. Constructed counterexamples defeat it, and they defeat every variant that names the pair by a structural rule. Whatever the balanced pair is, it does not appear to have a description.

Sorting under a partial order #

The sorting reading deserves its own section, because it is where the conjecture would be used and it explains why the constant matters.

Suppose $n$ things have a true total order and some comparisons have already been made, so what is known is a partial order $P$ with $e(P)$ extensions still consistent. Each further comparison of an incomparable pair splits $e(P)$ into two parts in the ratio $p : 1-p$, and the answer tells which part survives.

Information theory gives an immediate lower bound: at least $\log_2 e(P)$ comparisons are needed, because each one supplies at most one bit. The 1/3–2/3 conjecture would supply the matching upper bound. If a pair with $p$ between a third and two thirds always exists, comparing it multiplies the count by at most $\tfrac23$ whichever way it goes, so $\log_{3/2} e(P)$ comparisons suffice — a constant factor of about 1.71 above the information bound, and no more.

With the proved constant of $0.2764$ the factor is about 2.15 instead. So the conjecture is not about whether sorting under partial information is efficient — it is, either way — but about the exact constant, and about whether the natural bound is the true one. That is characteristic of the problem: everything practical is settled and the sharp statement is not.

This is the same accounting that gives the $n \log n$ bound for ordinary sorting, which is the special case $P$ empty: $e(P) = n!$, and $\log_2 n!$ is about $n\log_2 n$.

The correlation behind it #

One tool used on the problem is worth naming because it is a theorem of independent weight.

The XYZ inequality, proved by Shepp in 1982, says: in a random linear extension, the events $x$ comes before $y$ and $x$ comes before $z$ are positively correlated. Knowing that $x$ precedes $y$ makes it no less likely that $x$ precedes $z$.

That sounds obvious and it is not. Its proof uses the FKG inequality — a correlation result about monotone events on a distributive lattice — applied to the lattice of down-sets of the order. So a statement about sorting becomes a statement about a lattice, and the lattice is the one whose structure the whole of this ladder has been about — the down-sets of an order form a distributive lattice, and every finite distributive lattice arises this way, which is Birkhoff’s representation theorem and is why the two subjects are the same subject.

Preston and Fishburn had conjectured a strict form and it was open for years afterwards. The pattern is one this corner of the subject keeps producing: statements that are obvious, false-looking counterexamples that do not exist, and proofs that come from probability rather than from combinatorics.

Where the count is computable #

The general problem is intractable and a handful of shapes are not, and the list is short enough to give.

A disjoint union of two orders: the extensions are the interleavings, so the count is the product of the two counts times a binomial coefficient. The second figure above is this case.

A forest, where every element has at most one element directly above it: the hook length formula gives the count as $n!$ divided by a product over the elements, one factor each. Fast, exact, and the only tree-shaped closed form there is.

A product of two chains — a rectangle — where the extensions are counted by the standard Young tableaux of a rectangle, again a hook length formula. This is where the Catalan numbers appear: the extensions of a two-by-$n$ rectangle are counted by them.

Width two: an order cuttable into two chains has a count computable by a lattice-path argument, in polynomial time.

That is essentially the list. Everything else needs the exponential recursion, and the recursion is what the figures here run. A subject with four tractable shapes and one hardness theorem is a subject where the interesting work is approximation.

What the pictures cannot show #

Five elements, sixteen extensions. The figures compute everything by enumeration, and enumeration is available up to about a dozen elements. The theorem about hardness is a statement about what happens far beyond that.

The conjecture is checked and not proved. For each order drawn, the most balanced pair is found and asserted to lie between a third and two thirds. That is a verification on three orders, and the conjecture is about all of them.

The volume reading is described and not drawn. Linear extensions as congruent simplices in a cube is a picture that needs three dimensions to be even suggestive and $n$ to be honest.

Three orders, chosen to be small. The three shapes drawn have five, five and four elements. Nothing about them is representative — they were chosen because their extensions can be listed, which is exactly the property the general case does not have.

And the approximation algorithm is absent. The randomised counting scheme is a random walk on the set of extensions, and a figure of it would be a figure of one walk.

Where the ladder goes next #

This closes the ladder. It began by asking for the largest set of mutually incomparable elements and finding it to be a layer; it went on to the counting argument behind that, to the partition that upgrades the argument to a certificate, and to what happens when incomparable is replaced by intersecting.

It ends at a question with no answer. The extremal problems all have clean solutions and short proofs; the counting problem is complete for a class nobody can compute, and the most natural conjecture about it has been open for over fifty years. That is a fair summary of the subject: an order’s extremal structure is well understood and its arithmetic is not.

Sideways: the same gap between finding one object and counting all of them runs through the question of how many orderings there are of anything at all, and the sorting reading connects directly to the information bound. And the extremal side continues: the largest family in which every two members meet has a clean answer and a short proof, which is what every question on that side of the subject has.

What is worth carrying away #

Deciding, optimising and counting are three different problems about the same object, and their difficulty is not correlated.

For a partial order, finding one consistent ordering is linear time, finding the largest antichain is a matching, and counting the consistent orderings is complete for a class believed to be intractable. Nothing in the object’s definition predicts that. The hardness lives in the question, not in the structure — and a subject that has answered every extremal question about an object may not have answered the easiest-sounding one.