这是indexloc提供的服务，不要输入任何密码
Skip to main content
Springer Nature Link
Log in

Scaling Limits for Width Two Partially Ordered Sets: The Incomparability Window

  • Published:
Order Aims and scope Submit manuscript

Abstract

We study the structure of a uniformly randomly chosen partial order of width 2 on n elements. We show that under the appropriate scaling, the number of incomparable elements converges to the height of a one dimensional Brownian excursion at a uniformly chosen random time in the interval [0, 1], which follows the Rayleigh distribution.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+
from $39.99 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

References

  1. Aldous, D.: The continuum random tree III. Ann. Probab. 21(1), 248–289 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  2. Aldous, D., Steele, J.M.: The Objective Method: Probabilistic Combinatorial Optimization and Local Weak Convergence. Probability on Discrete Structures, Encyclopaedia Math. Sci., vol. 110, pp. 1–72. Springer, Berlin (2004)

  3. Angel, O., Schramm, O.: Uniform Infinite Planar Triangulations. Communications in Mathematical Physics, vol. 241, pp. 191–213 (2003)

  4. Baik, J., Deift, P., Johansson, K.: On the distribution of the length of the longest increasing subsequence of random permutations. J. Am. Math. Soc. 12, 1119–1178 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  5. Benjamini, I., Schramm, O.: Recurrence of Distributional Limits of Finite Planar Graphs. Electron. J. Probab. 6(23), 1–13 (2001)

    MathSciNet  Google Scholar 

  6. Bollobás, B.: Modern Graph Theory. Springer, Berlin (1998)

    Book  MATH  Google Scholar 

  7. Bollobás, B.: Random Graphs. Academic, London (1985)

    MATH  Google Scholar 

  8. Bollobás, B., Brightwell, G.: Box-spaces and random partial orders. Trans. Am. Math. Soc. 324, 59–72 (1991)

    MATH  Google Scholar 

  9. Bollobás, B., Brightwell, G.: The height of a random partial order: concentration of measure. Ann. Appl. Prob. 2, 1009–1018 (1992)

    Article  MATH  Google Scholar 

  10. Bollobás, B., Winkler, P.: The longest chain among random points in Euclidean space. Proc. Am. Math. Soc. 103(2), 347–353 (1988)

    MATH  Google Scholar 

  11. Brightwell, G.: Models of random partial orders. In: Walker, K. (ed.) Surveys in Combinatorics, London Math. Soc. Lecture Notes Series, vol. 187, pp. 53–83 (1993)

  12. Brightwell, G., Goodall, S.: The number of partial orders of fixed width. Order 13, 315–337 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  13. Daskalakis, C., Karp, R., Mossel, E., Riesenfeld, S., Verbin, E.: Sorting and selection in posets. In: Proceedings of SODA, pp. 381–391 (2009)

  14. Dhar, D.: Entropy and phase transitions in partially ordered sets. J. Math. Phys. 19(8), 1711–1713 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  15. Diaconis, P., Thiem, N.: Supercharacter Formulas for Pattern Groups. Trans. Am. Math. Soc. 361, 3501–3533 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  16. Durrett, R.: Probability: Theory and Examples. Duxbury Press (1996)

  17. Faigle, U., Turán, Gy.: Sorting and recognition problems for ordered sets. SIAM J. Comput. 17(1), 100–113 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  18. Feller, W.: An Introduction to Probability Theory and its Applications, vol. I. Wiley, New York-London-Sydney (1968)

    Google Scholar 

  19. Itô, K., McKean, H.P.: Diffusion Processes and their Sample Paths. Springer (1965)

  20. Janson, S., Luczak, T., Rucinski, A.: Random Graphs. Wiley (2000)

  21. Kaigh, W.D.: An invariance principle for random walk conditioned by a late return to zero. Ann. Prob. 4(1), 115–121 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  22. Kleitman, D.L., Rothschild, B.R.: Asymptotic enumeration of partial orders on a finite set. Trans. Am. Math. Soc. 205, 205–220 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  23. Kleitman, D.L., Rothschild, B.R.: A phase transition on partial orders. Phys. A 96, 254–259 (1979)

    Article  Google Scholar 

  24. Prömel, H.J., Steger, A., Taraz, A.: Phase transitions in the evolution of partial orders. J. Comb. Theory Ser. A 94(2), 230–275 (2001)

    Article  MATH  Google Scholar 

  25. Strimmer, K., Moulton, V.: Likelihood analysis of phylogenetic networks using directed graphical models. Mol. Biol. Evol. 17(6), 875–881 (2000)

    Article  Google Scholar 

  26. Strimmer, K., Wiuf, C., Moulton, V.: Recombination analysis using directed graphical models. Mol. Biol. Evol. 17(6), 875–881 (2000)

    Article  Google Scholar 

  27. Winkler, P.: Random orders. ORDER 1, pp. 317–331 (1985)

Download references

Author information

Authors and Affiliations

  1. Department of Statistics, University of California, Berkeley, CA, USA

    Nayantara Bhatnagar & Nick Crawford

  2. Department of Statistics and Department of Computer Science, University of California, Berkeley, CA, USA

    Elchanan Mossel

  3. Statistical Laboratory, University of Cambridge, Cambridge, UK

    Arnab Sen

Authors
  1. Nayantara Bhatnagar
    View author publications

    Search author on:PubMed Google Scholar

  2. Nick Crawford
    View author publications

    Search author on:PubMed Google Scholar

  3. Elchanan Mossel
    View author publications

    Search author on:PubMed Google Scholar

  4. Arnab Sen
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Nayantara Bhatnagar.

Additional information

N. Bhatnagar was supported by DOD ONR grant N0014-07-1-05-06 and DMS 0528488.

N. Crawford was supported by DMS 0548249 (CAREER).

E. Mossel was supported by DOD ONR grant N0014-07-1-05-06, DMS 0528488, DMS 0548249 (CAREER), and a Sloan Fellowship.

A. Sen was supported by DOD ONR grant N0014-07-1-05-06, DMS 0528488, and DMS 0548249 (CAREER).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bhatnagar, N., Crawford, N., Mossel, E. et al. Scaling Limits for Width Two Partially Ordered Sets: The Incomparability Window. Order 30, 289–311 (2013). https://doi.org/10.1007/s11083-011-9244-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue date:

  • DOI: https://doi.org/10.1007/s11083-011-9244-y

Keywords