Combinatorics, Probability and Computing


Order-Invariant Measures on Fixed Causal Sets


a1 Department of Mathematics, London School of Economics and Political Science, Houghton Street, London WC2A 2AE, UK (e-mail:

a2 School of Mathematics and Statistics, University of Sheffield, Hicks Building, Hounsfield Road, Sheffield S3 7RH, UK (e-mail:


A causal set is a countably infinite poset in which every element is above finitely many others; causal sets are exactly the posets that have a linear extension with the order-type of the natural numbers; we call such a linear extension a natural extension. We study probability measures on the set of natural extensions of a causal set, especially those measures having the property of order-invariance: if we condition on the set of the bottom k elements of the natural extension, each feasible ordering among these k elements is equally likely. We give sufficient conditions for the existence and uniqueness of an order-invariant measure on the set of natural extensions of a causal set.

(Received April 02 2010)

(Revised November 03 2011)

(Online publication January 19 2012)

AMS 2010 Mathematics subject classification:

  • Primary 06A07;
  • 60C05


Research carried out at the London School of Economics, and supported in part by a grant from STICERD.