Realizer of a poset problem

176 Views Asked by At

Let $P$ be a poset and let $R =\{L_1, L_2,\dots, L_t\}$ be a set of linear extensions of $P$. Then $R$ is a realizer of $P$ if and only if for all pairs of incomparable elements of $P$, $x$ and $y$, there are indices $i$ and $j$ so that $x < i <y$ and $x > j> y$. I have done the first part but using the 2nd condition, I cannot show that $R$ is realizer.

1

There are 1 best solutions below

0
On

Let $<_P$ the partial order on $P$. Since $L_1,\dots, L_t$ are linear extensions it is clear that $<_P\subseteq \bigcap L_i$, i.e., if $x<_P y$, then $x<_i y$ for every $y$.

For the other direction, assume that $x<_i y$ for every $i$. If $x$ and $y$ are incomparable in $P$, then there exist $i$ and $j$ such that $x<_i y$ and $y <_j x$, and hence $(x,y)\in\bigcap L_i$ if and only if $x=y$, which is a contradiction because they were incomparable. Therefore, they are comparable in $P$, whence the result.