On multipartite posets

DOI10.1016/J.DISC.2007.09.001MaRDI QIDQ2519843zbMATH OpenOpenAlexFDO

Authors Geir Agnarsson

Publication date 27 January 2009

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

bipartite posetlinear ordermultipartite posetorder dimension

Mathematics Subject Classification ID

Total orders (06A05) Partial orders, general (06A06) Combinatorics of partially ordered sets (06A07)

Abstract: A poset $mathbfP=(X,preceq)$ is {em $m$-partite} if $X$ has a partition $X=X_{1}cup\mathrm{...}cup{X}_m$ such that (1) each $X_i$ forms an antichain in $mathbfP$, and (2) $xprecy$ implies $xin{X}_i$ and $yin{X}_j$ where $i<j$. In this article we derive a tight asymptotic upper bound on the order dimension of $m$-partite posets in terms of $m$ and their bipartite sub-posets in a constructive and elementary way.

Review text

A poset \(P=(X,\leq )\) is called \(m\)-bipartite (\(m\geq 2\)) if \(X\) is a partition \(X=X_1\cup \dots\cup X_m\) such that \(X_i\) is an antichain in \(P\) and \(x<y\) implies \(x\in X_i\) and \(y\in X_j\), where \(i<j\). This notion is a generalization of that of a bipartite poset. The author derives a tight asymptotic upper bound on the order dimension of \(m\)-partite posets.

Recommendations

• scientific article; zbMATH DE number 3995740
• A bipartite analogue of Dilworth's theorem
• Partitioning posets
• Random bipartite posets and extremal problems
• DIMENSION AND INTERVAL DIMENSION OF CERTAIN BIPARTITE ORDERED SETS

Cites work

• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• On retractable sets and the fixed point property
• On the order dimension of convex polytopes
• Partially Ordered Sets
• The Complexity of the Partial Order Dimension Problem
• The dimension of interior levels of the Boolean lattice
• The Order Dimension of Convex Polytopes
• The order dimension of the complete graph
• The order dimension of two levels of the Boolean lattices

Cited in

(7)

• The numbers of shared upper bounds determine a poset
• Semi-pointed partition posets
• Positive Dependence, Upper Sets, and Multidimensional Partitions
• scientific article; zbMATH DE number 3995740 (Why is no real title available?)
• On \(n\)-normal posets
• A bipartite analogue of Dilworth's theorem
• Partitioning posets

This page was built for publication: On multipartite posets

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