2
$\begingroup$

Fix positive integers $k$ and $n$.

For which finite posets $(X,\lesssim)$ with $\#X=k$ does there exist an order embedding $\phi\colon(X,\lesssim)\to (\mathbb{R}^n,\le)$, where $\le$ is the standard partial order (product order) on $\mathbb{R}^n$?

Are there quantitative bounds on the minimal such $n$ for specific subclasses of these posets?

$\endgroup$
1

1 Answer 1

4
$\begingroup$

If $(P,\le)$ is a poset, the least $n$ such that $(P,\le)$ embeds into a product of $n$ total orders (or equivalently, such that $\le$ is the intersection of $n$ total orders on $P$) is known as the dimension of $(P,\le)$. If $P$ is finite, this is equivalent to embedding into the product of $n$ copies of any fixed infinite total order, such as $(\mathbb R,\le)$. Thus, the question is exactly about which posets of size $k$ have dimension at most $n$.

As Sam Hopkins notes in a comment, now banished to the netherworld, classifying posets of a given dimension is likely very hard. But for some basic bounds, all posets of size $k$ have dimension at most $k$, as $(P,\le)$ embeds to $(\mathcal P(P),\subseteq)\simeq\{0,1\}^k$ via $a\mapsto\{x\in P:x\le a\}$; on the other hand, the Wikipedia article gives an example of a poset of dimension $k/2$.

$\endgroup$
4
  • 1
    $\begingroup$ I thought links would be harmless, but, if you prefer to have them not in the post, then I apologise for editing them in. People can surely find the Wikipedia example themselves, but I'll link here to @SamHopkins's observation about the difficulty of classifying posets of a given dimension. $\endgroup$
    – LSpice
    Commented Mar 25 at 20:50
  • 2
    $\begingroup$ Linking to the same Wikipedia article twice is something I certainly find excessive. I didn't notice the comments on the question were meanwhile completely butchered by moderators (it's beyond my understanding what they find objectionable about the thread, which was on the whole quite constructive, and targeted at figuring out the intended question). In that case, I'll put the link back. $\endgroup$ Commented Mar 25 at 20:55
  • 2
    $\begingroup$ A survey from 1982 by Kelley and Trotter appears at trotter.math.gatech.edu/papers/31.pdf. There is also Trotter's book Combinatorics and Partially Ordered Sets available from amazon.com/Combinatorics-Partially-Ordered-Sets-Mathematical/dp/…. $\endgroup$ Commented Mar 25 at 23:44
  • $\begingroup$ Thank you. ${}$ $\endgroup$ Commented Mar 26 at 6:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .