We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Random bipartite posets and extremal problems.
- Authors
Biró, C.; Hamburger, P.; Kierstead, H. A.; Pór, A.; Trotter, W. T.; Wang, R.
- Abstract
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 relative tightness of the Füredi–Kahn upper bounds on dimension in terms of maximum degree; and (2) developing machinery for estimating the expected dimension of a random labeled poset on n points. For these reasons, 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 the results in the original paper deteriorated as p approaches 1. Motivated by two extremal problems involving conditions that force a poset to contain a large standard example, we were compelled to revisit this subject, but now with primary emphasis on the range 1 / 2 ≤ p < 1 . Our sharpened analysis shows that as p approaches 1, the expected value of dimension increases and then 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.
- Subjects
PARTIALLY ordered sets; EXPECTED returns; EXTREMAL problems (Mathematics); RECTANGLES
- Publication
Acta Mathematica Hungarica, 2020, Vol 161, Issue 2, p618
- ISSN
0236-5294
- Publication type
Article
- DOI
10.1007/s10474-020-01049-y