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.
Introduction
In the field of combinatorics, partially ordered sets (posets) are fundamental structures defined by a set of elements and a binary relation that is reflexive, antisymmetric, and transitive. A key parameter of any poset is its width, defined as the size of its largest antichain (a subset of elements where no two are mutually comparable). While the properties of random graphs are well-documented, the typical structure of random posets remains a challenging area of study.
This paper focuses on the "local geometry" of random posets with a fixed width of two. Specifically, it investigates the incomparability window: for a randomly chosen element, how many other elements in the poset are incomparable to it? Previous work by Brightwell and Goodall (1996) established asymptotic counts for width-2 posets, but did not characterize the distribution of these incomparable elements or the global height (the length of the longest chain) of a typical structure.
Combinatorial Foundations
The authors employ a rigorous combinatorial framework to analyze the set $\mathcal{P}_{n,2}$ of all labeled posets of size $n$ and width 2. A crucial first step is the reduction to "one-factor" posets. The authors prove that as $n \to \infty$, a typical width-2 poset consists of one giant connected component in its incomparability graph. This allows the analysis to focus on these simpler components without loss of generality.
To facilitate this analysis, the paper utilizes bijections between posets and labeled two-chain covers. As shown in Figure 1, a single unlabeled poset $P$ can correspond to multiple labeled configurations, which helps in counting and mapping the poset's relations to more tractable mathematical objects.
The Brownian Connection
The core innovation of the paper is a bijection between these two-chain covers and pairs of non-hitting random walks on an integer lattice. The relations within the poset are encoded as steps in two paths that are constrained never to cross or touch, except at their endpoints.
By applying the Invariance Principle, the authors demonstrate that as the number of elements $n$ grows, these discrete random walks converge to a Brownian excursion—a continuous stochastic process that starts and ends at zero while remaining positive in the interim. This mapping provides a geometric interpretation: the total number of incomparabilities in the poset corresponds to the area between the two random walk curves.
Key Results
The paper establishes two primary scaling limits:
-
The Incomparability Window (Theorem 1.1): For a random element $U_n$ in a random width-2 poset of size $n$, the number of incomparable elements $I_P(U_n)$, scaled by $\sqrt{n}$, converges in distribution to the height of a Brownian excursion at a random time: $$\frac{1}{\sqrt{n}} I_P(U_n) \xrightarrow{d} \frac{1}{\sqrt{2}} B^{ex}(U)$$ This limit follows a Rayleigh distribution with density $f(s) = 8se^{-4s^2}$ for $s > 0$.
-
Poset Height (Theorem 1.3): The height $h(P)$ of a random width-2 poset is shown to be concentrated around $n/2$, with Gaussian fluctuations: $$\frac{h(P) - n/2}{\sqrt{n}} \xrightarrow{d} |Z|$$ where $Z \sim N(0, 1/16)$.
Conclusion and Future Work
This research provides a complete description of the scaling limits for width-2 posets, revealing a deep connection between discrete order theory and continuous stochastic processes. However, the authors note that extending these results to posets of width $k > 2$ presents significant conceptual and technical hurdles. Future research may explore joint distributions of incomparable elements or seek to generalize these geometric constructions to higher-width structures.
Summary updated