Skip to main content
removed capitals from title
Link
YCor
  • 63.9k
  • 5
  • 187
  • 286

Find an Orderorder-Embeddingembedding of $S_3\times{\bf2}\times{\bf2}$ into ${\mathbb Z}^4$

Source Link
Tri
  • 1.6k
  • 10
  • 8

Find an Order-Embedding of $S_3\times{\bf2}\times{\bf2}$ into ${\mathbb Z}^4$

A function $f:P\to Q$ from a poset $(P,\le_P)$ to a poset $(Q,\le_Q)$ is an order-embedding if, for all $p,p'\in P$, $p\le_P p'$ if and only if $f(p)\le_Q f(p')$.

We partially order the Cartesian product $P\times Q$ of posets $(P,\le_P)$ and $(Q,\le_Q)$ as follows: for $(p,q),(p',q')\in P\times Q$, $(p,q)\le_{P\times Q}(p',q')$ if $p\le_P p'$ and $q\le_Q q'$. Similarly, we can define the product of more than two posets.

A chain is a poset $(C,\le)$ that is totally ordered: that is, for all $c,c'\in C$, either $c\le c'$ or $c'\le c$. For $n\in\mathbb N$, we denote the $n$-element chain by $\bf n$; its elements are $\{0,1,\dots,n-1\}$.

The dimension of a poset $P$ is the smallest number of chains into the product of which we can order-embed $P$.

Consider the poset $S_3:=({\bf 2}\times{\bf 2}\times{\bf 2})\setminus\{(0,0,0),(1,1,1)\}$. It is called the standard poset of dimension 3.

The poset $S_3\times{\bf 2}$ is shown in the figure below. The colors of the lines are merely for ease of reading.

enter image description here

If you put lines between the "corresponding" elements of the two parts of the diagram below, you will have $S_3\times{\bf 2}\times{\bf 2}$.

enter image description here

Find an order-embedding of $S_3\times{\bf 2}\times{\bf 2}$ into a product of 4 chains.

According to the middle of page 80 of Lin ("The dimension of the Cartesian product of posets," Discrete Mathematics 88 (1991), 79-92), there should be one.