Scaling limits for width two partially ordered sets: the incomparability window

DOI10.1007/S11083-011-9244-YMaRDI QIDQ1943695zbMATH OpenOpenAlexFDO

Authors Nayantara Bhatnagar, Nicholas Crawford, Elchanan Mossel, Arnab Sen

Publication date 20 March 2013

Published in Order (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0810.3670

zbMATH Keywords

scaling limitsBrownian excursionrandom posetswidth-2 partial order

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07)

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.

Recommendations

• The number of partial orders of fixed width
• Random k-dimensional orders: Width and number of linear extensions
• Random orders of dimension 2
• Improving the \(\frac{1}{3}\)-\(\frac{2}{3}\) conjecture for width two posets
• scientific article; zbMATH DE number 4091572

Cites work

• scientific article; zbMATH DE number 446489 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 2042286 (Why is no real title available?)
• scientific article; zbMATH DE number 3206627 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• An invariance principle for random walk conditioned by a late return to zero
• Asymptotic Enumeration of Partial Orders on a Finite Set
• Box-Spaces and Random Partial Orders
• Entropy and phase transitions in partially ordered sets
• On the distribution of the length of the longest increasing subsequence of random permutations
• Phase transitions in the evolution of partial orders
• Probability. Theory and examples.
• Recurrence of distributional limits of finite planar graphs
• Sorting and Recognition Problems for Ordered Sets
• Sorting and selection in posets
• Supercharacter formulas for pattern groups
• The Longest Chain Among Random Points in Euclidean Space
• The continuum random tree. III
• The height of a random partial order: Concentration of measure
• The number of partial orders of fixed width
• Uniform infinite planar triangulations

Cited in

(1)

• scientific article; zbMATH DE number 5592511 (Why is no real title available?)

This page was built for publication: Scaling limits for width two partially ordered sets: the incomparability window

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1943695)