Existence thresholds and Ramsey properties of random posets

Abstract

Let $\mathcal{P}(n)$ denote the power set of $[n]$, ordered by inclusion, and let $\mathcal{P}(n,p)$ denote the random poset obtained from $\mathcal{P}(n)$ by retaining each element from $\mathcal{P}(n)$ independently at random with probability $p$ and discarding it otherwise. Given any fixed poset $F$ we determine the threshold for the property that $\mathcal{P}(n,p)$ contains $F$ as an induced subposet. We also asymptotically determine the number of copies of a fixed poset $F$ in $\mathcal{P}(n)$. Finally, we obtain a number of results on the Ramsey properties of the random poset $\mathcal{P}(n,p)$.

33 pages, 2 figures. Author accepted manuscript, to appear in Random Structures and Algorithms