Are there partial orders (posets) of dimension $n$ with arbitrarily many linear extensions?

535 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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$.