3
$\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$
  • 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$ – Carl Mummert Nov 30 '17 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 '17 at 1:33
  • $\begingroup$ A similar construction would allow us to have any dimension $k > 1$. $\endgroup$ – Carl Mummert Nov 30 '17 at 1:37
  • $\begingroup$ Yes, this answers the question for $n=2$, but how would the construction proceed for $n>2$? $\endgroup$ – Joey Kilpatrick Nov 30 '17 at 1:54
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.