Random bipartite posets and extremal problems

Previously, Erdős, Kierstead and Trotter [5] investigated the dimension of random height 2 partially ordered sets. Their research was motivated primarily by two goals: (1) analyzing the relativetightness of the Füredi–Kahn upper bounds on dimension in terms ofmaximum degree; and (2) developing machinery for estimating theexpected dimension of a random labeled poset on n points. For thesereasons, most of their effort was focused on the case 0 < p≤ 1 / 2.While bounds were given for the range 1 / 2 ≤ p< 1 , the relative accuracy of theresults in the original paper deteriorated as p approaches 1. Motivated by two extremal problems involving conditions that force aposet to contain a large standard example, we were compelled torevisit this subject, but now with primary emphasis on the range1 / 2 ≤ p< 1. Our sharpened analysis shows that as papproaches 1, the expected value of dimension increases andthen decreases, answering in the negative a question posed in the original paper.Along the way, we apply inequalities of Talagrand and Janson,establish connections with latin rectangles and the Euler product function,and make progress on both extremal problems.