*This page is under development; eventually it will feature rather more
material, as well as more links to at least my own work on this subject.*

"Selected" means that I'm only going to tell you about research I have been involved with.

"Applications" means that the interest in the problem studied comes from the connection
to a practical problem, and not from the inherent beauty of the mathematics itself.

Gianpaolo Oriolo, Bruce Shepherd and I have written two papers on this subject:

Here are the Research Report versions. In both cases, the journal version was substantially revised following some very helpful comments from the referees, and you should probably read those instead.

LSE-CDAM-98-04

G. Brightwell, G. Oriolo, and F.B. Shepherd

Abstract Full report in compressed (gzip) PostScript format (128 kB)

LSE-CDAM-2000-03

G. Brightwell, G. Oriolo, and F.B. Shepherd

Abstract Full report in compressed (gzip) PostScript format (127 kB)

The approach we advocate in these papers is to look for a "diverse paths" reservation, consisting of a set of arc-disjoint paths, with enough capacity reserved so that we can meet the demand even if one path fails. It is straightforward to find the cheapest diverse paths reservation in the fractional case. However, the integer version of this problem is NP-hard. Our most eye-catching result (in the first paper) is that there is nevertheless an easy algorithm that finds a solution to the integer version of cost at most 15/14 times the optimum, and that 15/14 is the best possible.

What follows is a version from my own point of view, which is that of a pure mathematician.

The *Causal Set Hypothesis* in quantum gravity is that the ultimate structure of
spacetime is discrete, and that the only fundamental type of relationship between points
in spacetime is causality, enabling us to say that *x* is to the past of *y*,
or in the past light-cone of *y*.
This implies that the spacetime structure of the universe is that of a locally finite
partially ordered set, or "causal set". And a proper model for spacetime would be a
model of random causal sets.

The hope is that an appropriate model can be found, which on large scales approximates the classical structure of the universe, but on small scales gives rise to "quantum" effects. Of particular interest is the case where the causal set has a unique minimal element.

Quite a bit of attention has been paid to a class of models that are ultimately going
to be too simplistic - they are really designed to provide a "causal set" analogue to
the **classical** model of spacetime. These are called *classical sequential
growth (csg) models*, and were shown by Rideout and Sorkin to be the only models
satisfying some specific set of hypotheses.

A particular csg model is governed by a sequence of non-negative constants
(*t _{n}*). A random partial order on the set of natural numbers is
generated by choosing, for each

One of the reasons I am interested is that a very natural special case is that
of *random graph orders*, a model of random partial orders that I have done quite
a lot of work on over the years. To form a random graph order on the set of natural
numbers, take a random graph by joining each pair of vertices with some fixed
probability *p*, interpreting an edge as saying that the lower-numbered vertex
is below the higher, and taking the transitive closure. It's easy to see that this
corresponds to setting
*t _{n} = (p/1+p)^{n}*.

Moreover, the extra generality of csg models leads to
some questions that are fascinating purely as mathematics.
Some of these have been investigated by my research student Nic Georgiou, see:

LSE-CDAM-2003-17
**A Random Binary Order: A New Model of Random Partial Orders**

Nicholas Georgiou

Abstract
Full
report in compressed (gzip) PostScript format (356 kB)

My own work in this area goes back to a 1991 paper with Ruth Gregory,
"Structure of Random Discrete Spacetime", *Physical Review Letters* **66** 260-263.
What we show here is that, if you form a random partial order by taking a piece of a
Lorentzian manifold, and selecting points at random according to a Poisson process, then you
can recover an approximation to the distance between timelike points purely from the order
structure on the discrete set. Starting with the manifold is nowadays regarded in some circles
as cheating: you really want to start with a simple law, and demonstrate that the manifold
structure emerges.

More recently, I have been working with Fay Dowker, Raquel Garcia, Joe Henson and
Rafael Sorkin on topics relating to csg models.
This has resulted (so far) in two papers, which can be found here:

General Covariance and the
"Problem of Time" in a Discrete Cosmology

"Observables" in causal set cosmology

What we prove is a little technical: read the papers if you are interested. By the way,
even though I'm a pure mathematician and my co-authors are physicists, it is most
definitely **not** the case that I am responsible for all the proofs!

And what does this have to do with me being at the London School of Economics? Well, I'm not going to try too hard to concoct a link, and indeed I don't put papers on "cosmology" into the LSE-CDAM Research Report Series. But this is a potentially interesting application area that throws up interesting questions in an area of mathematics I know a lot about, which is why I work on it. Furthermore ...

... some time ago, Noga Alon, Béla Bollobás, Svante Janson and I wrote a paper:

Linear extensions of a random partial order, *Annals of Applied Probability* **4**
(1994) 108-123.

The main result of this paper is that, almost surely, a random graph order has infinitely
many *posts*, elements of the partial order that are comparable with all others. There
have been other papers since, refining this result in various ways. We were motivated to work
on this problem purely because we thought it was a natural question about a natural random
combinatorial model. If you think that the structure of csg models might in any way be
analogous to the structure of spacetime (a premise that I personally regard as highly dubious),
then the appearance of a post corresponds to a new "cycle" of the universe. So the question
of whether random graph orders have posts turns out to have potentially important applications.

This is, ultimately, what research in pure mathematics is supposed to be all about, isn't it?

Graham Brightwell

Last change: 1 April 2004