Selected Applications

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.

Resilient Networks

Suppose we want to guarantee that a certain amount of flow is available from one node of a network to another, even on the failure of one (or more) arc. One particular model is that where we have to reserve capacity ahead of time, paying for each unit of capacity on each arc (different arcs may have different per-unit costs); how should we do this in the cheapest possible way?

Gianpaolo Oriolo, Bruce Shepherd and I have written two papers on this subject:
Reserving resilient capacity in a network, SIAM J. Disc. Maths 14 (2001) 524-539.
Reserving resilient capacity for a single commodity with upper-bound constraints, Networks 41 (2003) 87-96.

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 Some Strategies for Reserving Resilient Capacity
G. Brightwell, G. Oriolo, and F.B. Shepherd
Abstract [file] Full report in compressed (gzip) PostScript format (128 kB)

LSE-CDAM-2000-03 Reserving Resilient Capacity with Upper Bound Constraints
G. Brightwell, G. Oriolo, and F.B. Shepherd
Abstract [file] 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.

Causal Sets

Here is a good introduction to this subject: Causal Sets: Discrete Gravity, by Rafael Sorkin.

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 (tn). A random partial order on the set of natural numbers is generated by choosing, for each n, a set Sn of predecessors of n, with the probability of Sn = A being proportional to t|A|, and then taking the transitive closure.

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
tn = (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 [file] 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?

The Transportation Polytope

Computational Learning Theory

Graham Brightwell

Last change: 1 April 2004