5
$\begingroup$

By dimension, I use the definition that was formulated by Dushnik and Miller: If $P$ is a partial order, then the dimension of $P$ is the minimum number of linear extensions of $P$ whose intersection is exactly $P$.

A, not nessecarily minimum, set of linear extensions whose intersection is exactly $P$ is called a realizer.

Intuitively, as the number of linear extensions increases, the number of possible realizers increases, possibly decreasing the dimension.

EDIT:

$n=1$: The answer is no. The only partial orders with dimension $1$ are already linear orders, so every dimension $1$ poset has only one linear extension.

$n=2$: As mentioned by @CarlMummert, antichains of size $m$ have dimension $2$ and have $m!$ linear extensions, so there exist posets of dimension $2$ with arbitrarily many linear extensions.

$\endgroup$
4
  • 1
    $\begingroup$ Suppose that our poset $P$ consists only of an antichain with $m$ elements $a_1, \ldots, a_m$. Then there are $(m)!$ linear extensions. Now consider one linear extension $a_1 < a_2 < \cdots < a_m$ and another $a_m < a_{m-1} < \cdots< a_2 < a_1$. If $i < j$ there is no relation $a_i < a_j$ that is present in both linear extensions, so the intersection of the extensions is exactly $P$. So the dimension of $P$ is $2$. Hence there are partial orders of dimension $2$ with arbitrarily many linear extensions. If this is not what you are looking for, could you clarify the question? $\endgroup$ Nov 30, 2017 at 1:32
  • $\begingroup$ What is the dimension of the trivial ($x\le y\iff x=y$) partial order? I think it's $2$ and it has lots of linear extensions. $\endgroup$
    – bof
    Nov 30, 2017 at 1:33
  • $\begingroup$ A similar construction would allow us to have any dimension $k > 1$. $\endgroup$ Nov 30, 2017 at 1:37
  • $\begingroup$ Yes, this answers the question for $n=2$, but how would the construction proceed for $n>2$? $\endgroup$ Nov 30, 2017 at 1:54

1 Answer 1

0
$\begingroup$

I have resolved the question, but will post my findings here:

The answer is yes, there exist posets of each dimension $n\ge 2$ with arbitrarily many linear extensions. Consider the following two procedures.

$\textbf{Method 1:}$

Input: Poset on $k$ elements with dimension $n\ge 2$ and $c$ linear extensions.

Output: Poset on $k+1$ elements with dimension $n\ge 2$ with $c(k+1)$ linear extensions.

Make a new poset $Q$ by taking the union of the $k$ elements of the input poset $P$ and $x\notin P$ (take the reflexive closure to make this a poset). This new poset has $k+1$ elements. Output this poset.

Correctness: Consider a minimum size realizer of $P$. Pick any linear extension in the realizer and create a new linear order on $P\cup \{x\}$ by appending $x$ to the bottom such that the new linear order is compatible with the original linear extension and such that $x$ is under every other element. For every other linear extension in the realizer, do the same but append $x$ to the top such that every element in $P$ is under $x$. It is easy to show that this set of new linear extensions of $Q$ is a realizer.
Consider the set of $c$ linear extensions of $P$. For each linear extension, it is possible to create $k+1$ new linear extensions of $Q$ by appending $x$ to the top, bottom, or between two adjacent elements. Therefore $Q$ has $c(k+1)$ linear extensions.

$\textbf{Note on Method 1:}$

This method answers the original question, but motivates a slightly more specific question: Are there connected partial orders of dimension $n$ with arbitrarily many linear extensions? The following method gives an affirmative answer.

$\textbf{Method 2:}$

Input: Poset with dimension $n$ with $c$ linear extensions.

Output: Poset with dimension $n$ with $c^2$ linear extensions.

Make two copies of the input poset, $P_1$ on the set $\{u_1, u_2\,...,u_k\}$ and $P_2$ on the set $\{v_1, v_2\,...,v_k\}$. Output a new poset $Q=(P_1 \cup P_2,\le)$ with $x\le y$ if and only if one of the following is true:
$(1)$ $x,y$ are both in $P_1$ and $x$ is under $y$ in $P_1$
$(2)$ $x,y$ are both in $P_2$ and $x$ is under $y$ in $P_2$
$(3)$ $x$ is in $P_1$ and $y$ is in $P_2$.

Correctness: Consider a minimum size realizer of the input poset. Make two copies of this realizer, one on $P_1$ and one on $P_2$. Pair each of the $n$ elements of the $P_1$ realizer with an element of the $P_2$ realizer. For each pair, make a new linear order on $P_1 \cup P_2$ with every element of $P_1$ under every element of $P_2$. It is easy to show that this set of new linear orders is an $n$ element realizer for $Q$, so $dim(Q)\le n$. Since $Q$ has a subposet with dimension $n$,then $dim(Q)\ge n$. Therefore, $dim(Q)=n$.
Notice that in every linear extension of $Q$, every $u_i$ is under every $v_i$. Also, notice that the linear extensions of $Q$ are exactly the linear extensions of $P_1$ under the linear extensions of $P_2$. Since there are $c$ linear extensions for $P_1$ and $P_2$, there are $c^2$ possible linear extensions of $Q$.

$\endgroup$

You must log in to answer this question.

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