Random bipartite posets and extremal problems

DOI10.1007/S10474-020-01049-YMaRDI QIDQ2220979zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 25 January 2021

Published in Acta Mathematica Hungarica (Search for Journal in Brave)

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

zbMATH Keywords

dimensionposetstandard examplebipartite posetrandom bipartite graph dimension

Mathematics Subject Classification ID

Partial orders, general (06A06) Extremal problems in graph theory (05C35) Combinatorics of partially ordered sets (06A07)

Abstract: Previously, ErdH{o}s, Kierstead and Trotter 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"{u}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<ple1/2$. While bounds were given for the range $1/2lep<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/2lep<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.

Recommendations

• The dimension of random ordered sets
• On poset similarity
• On an extremal problem for poset dimension
• Forcing posets with large dimension to contain large standard examples
• Large subposets with small dimension.

Cites work

• scientific article; zbMATH DE number 4085656 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3318593 (Why is no real title available?)
• Better bounds for poset dimension and boxicity
• Dimension for posets and chromatic number for graphs
• Forcing posets with large dimension to contain large standard examples
• On the dimensions of ordered sets of bounded degree
• On the independence number of random graphs
• Partially Ordered Sets
• Standard examples as subposets of posets.
• The dimension of random ordered sets
• The probabilistic method

Cited in

(6)

• Small scalar multiplication on Weierstrass curves using division polynomials
• Standard examples as subposets of posets.
• Random posets, lattices, and lattices terms
• The dimension of random ordered sets
• Forcing posets with large dimension to contain large standard examples
• On multipartite posets

This page was built for publication: Random bipartite posets and extremal problems

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