Partially Ordered Sets

This page is under development.

A large proportion of my research over the years has been connected with finite partially ordered sets. Here I collect what I've done into themes; the plan is to give a description of at least some of my papers in each area, but for now only the first section is more than a list of lists.

Tom Trotter and I are writing a book on finite partially ordered sets, which is taking rather longer to do than we were hoping/expecting/wanting. But it will appear.

Correlation Inequalities


Suppose you have an unknown linear order on a finite set X, and some information about it in the form of a partial order P on X. You can then think of each linear extension of P as a candidate for the unknown linear order, and in the absence of any other information it is reasonable to treat these as `equally likely'. The set of linear extensions of P is then a (simple) probability space, and we can ask questions about it in that light.

We say that two events A and B are positively correlated (with respect to P) if Pr(A) Pr(B) < Pr(A and B). This means that, if we condition on the occurence of A, it becomes more likely that B occurs as well.

The archetypal `correlation inequality' is the famous XYZ inequality of Shepp (1982): for any elements x,y,z, the events x < y and x < z are non-negatively correlated with respect to any poset P: in other words, if we learn that x is below some element y, that makes it no less likely that x is also below element z. This ought to sound obvious, but no truly short proof is known. In 1984, Fishburn proved that the correlation is strict except in really trivial cases (e.g., if we already know that x < y).

Much of the work in my PhD thesis was about correlation inequalities, and this work makes up the first three papers below.

My first paper:
Universal correlations in finite posets, Order 2 (1985) 129-144
addresses the question of when two sets of relations are always non-positively correlated, no matter what initial information (the poset P) we have. For instance, the set consisting of just the relation x < y , and the set consisting of just the relation z < x, are always non-positively correlated. The basic theme is that this, and other similar results that can easily be derived from it, is just about all that is true.

My second paper has a terrible title:
Some correlation inequalities in finite posets, Order 2 (1986) 387-402.
Here's what it's actually about. You can't expect a good answer to the question: with respect to which P are the events x < y and u < v positively correlated? (Because, for any given poset P, it's true for about half the choices of labels, and it's computationally intractable to figure out which.) But you could try asking: for which P are the events x < y and u < v positively correlated with respect to all orders extending P? The XYZ inequality gives one (in this context, trivial) instance of this. A more interesting result along these lines is due to Graham, Yao and Yao: x < y and u < v are positively correlated whenever P is the union of two chains, one containing x and u, the other containing y and v. (The point is that, if P has this form, then so does every extension of P.) It's traditional to motivate this by talking about teams of tennis players: suppose we know everything about the ranking of players within our two teams, and maybe partial information about the ranking of players in different teams. Now someone on my team beats someone on your team: that can't make it less likely that I will beat you. Anyway, the basic theme is that this is just about the only example (sort of). Along the way, I showed that the GYY inequality holds strictly except in trivial cases.

Now here's a better title:
Events correlated with respect to every subposet of a fixed poset, Graphs and Combinatorics 6 (1990) 111-131.
I now forget who it was - perhaps the referee - who insisted that my original title `On correlation and partially ordered sets' wasn't remotely informative enough. My thanks to them, whoever and wherever they are.

So this is the obvious companion question to the one described above. This time the stem result is: if we have two teams of tennis players, and we know nothing about the relative ability of any pair of players on different teams, although we may know something about the ranking within a team, then learning that a player on my team has beaten a player on your team makes it no less likely that I will beat you. Rewritten as mathematics, this is another result of Shepp. The basic theme of my paper is that this is just about the only example where x < y and u < v are non-negatively correlated with respect to P and all its subposets (well, sort of). Along the way, I showed that Shepp's inequality holds strictly except in trivial cases.

An annoying feature of all correlation results in this area was that they used as a tool the Ahlswede-Daykin Four Functions Theorem (or some other closely related result), which starts "Let L be a distributive lattice...". The method of proof is always to impose a distributive lattice structure on the set of linear extensions, or some variant, and then apply the Four Functions Theorem or one of its relatives to get the required result. Shepp's proof of the XYZ inequality is the absolute classic argument of this type.

But, if you are confronted by a problem for which no distributive lattice structure suggests itself, then what? Apparently you are stuck, and indeed there are various conjectures that have just as strong an intuitive basis as the results I have described above, but which seem much harder.

So, it is of some interest to find "elementary" proofs of some or all of the results mentioned above, especially the XYZ inequality. (There are several elementary proofs of GYY known.) The point is not that the Four Functions Theorem is a tremendously difficult theorem to prove (in fact, it is surprisingly easy to prove: the hard part is thinking of it in the first place), so that using it makes the result obtained seem misleadingly "deep". It's more that alternative techniques might be more widely applicable.

That's the motivation underlying this more recent paper, written jointly with Tom Trotter:
A combinatorial approach to correlation inequalities, Discrete Math. 257 (2002) 311-327.
Here's the research report version, which isn't too different from the published one:

LSE-CDAM-99-10 A Combinatorial Approach to Correlation Inequalities
Graham R. Brightwell and William T. Trotter
Abstract [file] Full report in compressed (gzip) PostScript format (88 kB)

One of the things we do here is provide an elementary (which is not to say easy, or intuitive) proof of Fishburn's strict XYZ inequality. Here's the basic plan. A correlation inequality can be expressed as asserting that the product |A| |D| of the sizes of two sets is at most the product |B| |C| of the sizes of two other sets, and a natural thing to try is to find an explicit injection from (A x D) to (B x C). But it's perfectly valid to take another set E, and find an injection from (A x D x E) to (B x C x E). How can this possibly be easier? Well, read the paper.

When you've read the paper, Tom and I would be thrilled if you could use this method to prove any result that wasn't previously known.


Covering Graphs/Diagrams


(with B. Bollobás and J. Nesetril) Random graphs and covering graphs of posets, Order 3 (1986) 245-255.

(with J. Nesetril) Reorientations of covering graphs, Discrete Math. 88 (1991) 129-132.

On the complexity of diagram testing, Order 10 (1993) 297-303.


Counting Linear Extensions


This includes papers related to the 1/3-2/3 Conjecture.


A linear extension of a partially ordered set is a linear order on the same groundset that extends the partial order, i.e., whenever x < y in the partial order, then x is also below y in all linear extensions.
Given a partially ordered set, how hard is it to count the number of linear extensions? There are a few special cases where there is a simple algorithm, notably if the partial order has fixed small width. But Peter Winkler and I proved that is hard in general. Specifically, it's #P-complete, meaning that it's as hard as counting the number of satisfying assignments of an instance of SAT.

(with P. Winkler) Counting linear extensions, Order 8 (1991) 225-242. (An extended abstract also appears as "Counting linear extensions is #P-complete", Proc. 23rd ACM Symposium on the Theory of Computing (STOC) (1991) 175-181.


But it is not too hard to approximate the number of linear extensions. This is because the number of linear extensions of an n-element partial order P is equal to n! times the volume of either the order polytope or the chain polytope of P, and there is a fully polynomial randomised approximation scheme (fpras) for finding the volume of a well-specified convex body, as first proved by Dyer, Frieze and Kannan.
The idea of approaching counting the number of linear extensions by looking at, in particular, the chain polytope, seems to be a fruitful one. There is a lovely paper by Kahn and Kim on this subject, and here are two of my own papers on a similar theme.

(with B. Bollobás and A. Sidorenko) Geometrical techniques for estimating numbers of linear extensions, European J. Combinatorics 20 (1999) 329-335.

(with B. Bollobás) Convex bodies, graphs and partial orders, Proc. London Math. Soc. (3) 80 (2000) 415-450.


One of the best-known open problems in the theory of partially ordered sets is the so-called 1/3-2/3 Conjecture. This states that, in any partially ordered set that is not a linear order, there is some pair x,y of elements such that the proportion of linear extensions in which x is above y lies between 1/3 and 2/3. The partial order with three elements and one related pair shows that 1/3-2/3 would be best possible.
One reason this is interesting is in the context of sorting algorithms; if the partial order represents the state of knowledge about an unknown linear order on a set, then someone seeking to sort the set efficiently using pairwise comparisons should look for a pair of elements x,y that is "balanced", in the sense that x is above y in about half of the linear extensions, and compare those. The point is that, whatever the outcome of the comparison, the number of candidates for the linear order (i.e., linear extensions) is reduced by a factor of nearly two.
I've written a number of papers on this problem, including this survey article:

Balanced pairs in partial orders, Discrete Math. 201 (1999) 25-52.


The next paper introduces a version of the conjecture for countably infinite, locally finite, partially ordered sets:

Linear extensions of infinite posets, Discrete Math. 70 (1988) 113-136.

In the paper above, I prove that, if there is some fixed k such that every element of the partially ordered set is incomparable with at most k others, then the notion of "proportion of linear extensions with x below y" extends naturally to the infinite case. In this context, there is an infinite "ladder-like" partial order in which no pair is more "balanced" than .7236-.2764. Stefan Felsner, Tom Trotter and I proved that this is the worst case for the infinite version of the problem:
(with S. Felsner and W.T. Trotter) Balancing pairs and the cross-product conjecture, Order 12 (1995) 327-349.
Curiously, this is also at present the best bound for the finite case. The lesson seems to be that balanced pairs can be quite rare, and one can't hope to prove the 1/3-2/3 Conjecture by any sort of "averaging" argument; instead one needs to argue about the "top" or "bottom" of the partial order, and no-one has found an effective way to do that.

In some of my earlier papers, the 1/3-2/3 Conjecture is proved for some special cases. In the paper below, it is proved for semiorders:
Semiorders and the 1/3-2/3 conjecture, Order 5 (1989) 369-380.

In this paper it is proved for partial orders such that every element is incomparable with at most 5 others:
(with C.D. Wright) The 1/3-2/3 conjecture for 5-thin posets, SIAM J. Disc. Maths. 5 (1992) 467-474.

Here are two more miscellaneous papers:
(with P. Fishburn and P. Winkler) Interval orders and LEM cycles, Ars Combinatoria 36 (1993) 283-288.
We show that there is an interval order containing three elements x,y,z with x < y in more than half the linear extensions, y < z in more than half the linear extensions, and z < x in more than half the linear extensions. Such a thing is called a "LEM [Linear Extension Majority] cycle" and there are a number of papers by Peter Fishburn showing that they can be found in various types of partial order.

(with P. Tetali) The number of linear extensions of the boolean lattice, Order 20 (2003) 333-345.
We prove some sharp bounds on the number of linear extensions of the boolean lattice.


Geometric Representations


Suppose you have a 3-connected planar graph. Then it is well-known that the graph can be drawn in the plane with straight-line edges. What Ed Scheinerman and I prove in:
Representations of planar graphs, SIAM J. Disc. Maths. 6 (1993) 214-229
is that you can also simultaneously draw the planar dual with straight-line edges, in such a way that edges cross dual edges at right angles. This answered a question asked by Tutte in 1963. In fact, it's even nicer than that. To find out more, either read our paper or see the book "Graphs on Surfaces" by Mohar and Thomassen. Scheinerman and I were the first to publish a proof of this result, but it seems that several people proved similar results at about the same time.

A preprint version of this paper has the distinction of being LSE-MPS-1, the first entry in the LSE's Mathematics Preprint Series (now the CDAM Research Report Series).

Scheinerman and I arrived at our result by thinking about circle orders. A circle order is a partial order that can be represented by discs in the plane, with the order given by containment. You can make similar definitions for other geometric objects, and come up with notions of square order, hexagon order, and the like. Or you can go up to higher dimensions and think about sphere orders -- orders represented by balls in R3 -- and so on.

I think this is an utterly natural concept, and here is another reason it's interesting. Take 4-dimensional Minkowski space, i.e., the standard model of flat spacetime. (A quick definition is that it consists of pairs (x,t), where x is in R3 and t is a real number, with (x,t) < (x',t') if t'-t > ||x - x'||.) Which finite partial orders can be embedded in this space?

The answer is exactly sphere orders. This is easy to see: imagine taking a finite partial order embedded in 4-dimensional Minkowski space, consider a horizontal hyperplane below all the points, and identify each point of the space with the sphere consisting of those points in the hyperplane below it. Then one point of Minkowski space is below another if its sphere is contained in the other sphere.

It would be nice to know more about sphere orders than we do. We know little enough about circle orders, which are surely easier to deal with.

I intend to expand on this here, but for now here are two papers I have written a while back.

(with P. Winkler) Sphere orders, Order 6 (1989) 235-240.
This paper gives a construction, for each k, of a partial order that can be represented by balls in Rk but not by balls in Rk-1. We have rather few concrete examples of partial orders that aren't, say, sphere orders, although a result of Alon and Scheinerman implies that the number of n-element sphere orders grows no faster than about n4n.

(with E. Scheinerman) The dual of a circle order is not necessarily a circle order, Ars Combinatoria 41 (1995) 240-246.
We prove the result stated in the title. Here "dual" just means you reverse the order. More on the significance of this will appear here at some stage.


Random Partial Orders


There are three basic models of random partially ordered sets.

At least, that was a convenient way of organising the material in my survey article:
Models of random partial orders in Surveys in Combinatorics 1993 (K. Walker Ed.) Cambridge University Press (1993) pp.53-83.
(This is the volume associated with the 1993 British Combinatorial Conference.)


Model 1: declare each n-element partial order to be equally likely. What you discover (or rather, what Kleitman and Rothschild discovered in 1975) is that all but a vanishing proportion of n-element partial orders have height 3. My papers on (or around) this model are as follows.

Linear extensions of random orders, Discrete Math. 125 (1994) 87-96.

(with H.-J. Promel and A. Steger) The average number of linear extensions of a partial order, J. Combinatorial Theory (A) 73 (1996) 193-206.


Model 2: take k linear orders on [n], independently and uniformly at random, and intersect them. These "random k-dimensional orders" were introduced and studied by Peter Winkler. My papers on (or around) this model are as follows.

(with B. Bollobás) Box-spaces and random partial orders, Trans. Amer. Math. Soc. 324 (1991) 59-72.

(with B. Bollobás) The height of a random partial order: concentration of measure, Annals of Applied Probability 2 (1992) 1009-1018.

Random k-dimensional orders: width and number of linear extensions, Order 9 (1992) 333-342.

(with B. Bollobás) Random high dimensional orders, Adv. Appl. Prob. 27 (1995) 161-184.


Model 3: take a random graph on [n], regard each edge ij as putting the lower-numbered of i and j below the higher-numbered, and take the transitive closure. These "random graph orders" were introduced and studied by Albert and Frieze. My papers on (or around) this model are as follows.

(with N. Alon, B. Bollobás and S. Janson) Linear extensions of a random partial order, Annals of Applied Probability 4 (1994) 108-123.

Random graph orders do not satisfy a 0-1 law, Random Structures and Algorithms 6 (1995) 231-237.

(with B. Bollobás) The width of random graph orders, The Mathematical Scientist 20 (1995) 69-90.

(with B. Bollobás) The dimension of random graph orders, in The Mathematics of Paul Erdos II, (R.L. Graham and J. Nesetril Eds.) pp.51-69, Springer 1996.

(with B. Bollobás) The structure of random graph orders, SIAM J. Disc. Maths. 10 (1997) 318-335.


Asymptotic Enumeration Problems


(with S. Goodall) The number of partial orders of fixed width, Order 13 (1996) 315-337.

(with D. Grable and H.-J. Promel) Forbidden induced partial orders, Discrete Math. 201 (1999) 53-80.


Dimension Theory


(with E. Scheinerman) Fractional dimension of partial orders, Order 9 (1992) 139-158.

(with W.T. Trotter) The order-dimension of convex polytopes, SIAM J. Disc. Maths. 6 (1993) 230-245.

(with W.T. Trotter) Incidence posets of trees in posets of large dimension, Order 11 (1994) 159-167.

(with H. Kierstead, A. Kostochka and W.T. Trotter) The dimension of suborders of the Boolean lattice, Order 11 (1994) 127-134.

(with P. Franciosa) On the Boolean dimension of spherical orders, Order 13 (1996) 233-243.

(with W.T. Trotter) The order-dimension of planar maps, SIAM J. Disc. Maths 10 (1997) 515-528.



Graham Brightwell

Last change: 5 January 2005