Onset of the Asymptotic Regime for (Uniformly Random) Finite Orders

ABSTRACT

We describe a Markov Chain Monte Carlo algorithm which can be used to generate naturally labeled n-element posets at random with a probability distribution of one’s choice. Implementing this algorithm for the uniform distribution, we explore the approach to the asymptotic regime in which almost every poset takes on the three-layer structure described by Kleitman and Rothschild (KR). By tracking the n-dependence of several order-invariants, among them the height of the poset, we observe an oscillatory behavior which is very unlike a monotonic approach to the KR regime. Only around n = 40 or so does this “finite size dance” appear to give way to a gradual crossover to asymptopia which lasts until n = 85, the largest n we have simulated.

KEYWORDS:

• asymptotic enumeration
• causal sets
• Markov Chain Monte Carlo
• order
• partially ordered sets

2000 AMS SUBJECT CLASSIFICATION:

• 05A16
• 06-04
• 06A07
• 83C45

Acknowledgments

We are grateful to a number of people for comments and suggestions, including Samo Jordan, Lisa Glaser, Andrzej Gorlich, Denjoe O’Connor, Jeff Remmel, Orest Bucicovschi, and Graham Brightwell.

We thank Yaakoub El Khamra for his encouragement and assistance with profiling our code on Lonestar (www.tacc.utexas.edu/resources/hpc/lonestar). Early trials were conducted on the HPC cluster at the Raman Research Institute.

Funding

This work was funded by a grant from the Foundational Questions Institute (FQXi) Fund on the basis of proposal FQXi-RFP3-1018. This work was also supported in part under an agreement with Theiss Research and funded by a grant from the FQXi Fund on the basis of proposal FQXi-RFP3-1346 to the Foundational Questions Institute. The FQXi Fund is a donor-advised fund of the Silicon Valley Community Foundation. This research was also supported in part by NSERC through grant RGPIN-418709-2012. This research was additionally supported in part by Perimeter Institute for Theoretical Physics. Research at Perimeter Institute is supported by the Government of Canada through Industry Canada and by the Province of Ontario through the Ministry of Research and Innovation. JH also receives support from EPSRC grant DIQIP and ERC grant NLST. This material is based in part upon work supported by DARPA under Award No. N66001-15-1-4064. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of DARPA. This work used the Extreme Science and Engineering Discovery Environment (XSEDE), which is supported by National Science Foundation grant number ACI-1053575.

Notes

1 Technically, a time-oriented Lorentzian geometry which contains no closed causal curve.

2 An upper-triangular bit-matrix M defines a binary relation on [n] via the rule j≺k⇔M_jk = 1. If one adds the condition of transitivity, then M yields a general element of Ω_n.

3 We also experimented with a third move inspired by the dynamics of “transitive percolation” [Rideout and Sorkin 00]. However, it did not seem to speed up the thermalization of the Markov chain.

4 1≺2≺6≺15, so each would have to lie in the corresponding layer X_i, i = 1…4. Likewise with 1≺5≺7≺12. However 2⊀12, which violates condition (2).

5 For computational convenience, we have used here levels as proxies for layers. For this partitioning, condition (1) holds trivially.

6 “Expected” but not “predicted”, since we understood the significance of natural vs. arbitrary labelings only after seeing this curve!

7 The observables would still be measured on the transitive closure of the directed graph, its “projection down to Ω_n”.