*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.

Suppose you have an unknown linear order on a finite set

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
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.

(with B. Bollobás and J. Nesetril)

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

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

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.

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:

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
**R**^{3} -- 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 **R**^{3} 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 **R**^{k} but not by balls in
**R**^{k-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 *n ^{4n}*.

(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.

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.

(with S. Goodall)

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

(with E. Scheinerman)

(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