A poset $P$ is series-parallel iff it contains no subset isomorphic to $Z_4$

60 Views Asked by At

I'm trying to prove that a finite poset is series-parallel (i.e. it can be built up from a one-element poset using disjoint union and ordinal sum of posets) iff it contains no subset isomorphic to $Z_4$ the zig-zag poset ($x_1\leq x_2, x_3\leq x_2, x_3\leq x_4$), which is an N-shaped poset.

It's easy to check that this is the only poset of four elements which isn't series-parallel. I tried proving this by induction on the number of elements of the poset, let $P$ be a poset with $n+1$ elements, if $P$ isn't connected then everything follow easly.

If $P$ is connected how do I continue?

1

There are 1 best solutions below

0
On BEST ANSWER

Indeed, you can prove this by strong induction on $n$. The base case is easy, so assume that for all $m$ such that $1\le m\le n-1$, that a poset on $m$ elements is series-parallel if and only if it does not contain $Z_4$.

It is easiest to prove he forward implication, that a series-parallel poset does not contain $Z_4$. Every series parallel poset with more than one element is either of the form $P+Q$ (ordinal sum) or $P\sqcup Q$ (disjoint sum), where $P$ and $Q$ are series-parallel posets. As you mentioned, in the $P\sqcup Q$ case, we know by induction that neither $P$ nor $Q$ contains $Z_4$, and there clearly cannot be a $Z_4$ which intersects $P$ and $Q$. Similar logic applies in $P+Q$ case; in order for $\{v_1,v_2,v_3,v_4\}$ to be $Z_4$, you would need have two of the elements in the $P$ part, and the other two in the $Q$ part, but then both of the maximal elements would be larger than the minimal ones, so this is not isomorphic to $Z_4$.

The hard part is to prove the reverse implication, that a $Z_4$-avoiding poset is series-parallel. Let $P$ be a poset which avoids $Z_4$. If $P$ is disconnected, so that $P=P_1\sqcup P_2$, then clearly both $P_1$ and $P_2$ avoid $Z_4$ as well, so by induction we conclude $P_1$ and $P_2$ are series-parallel, so $P$ is series-parallel as well.

Assume, on the other hand, $P$ is connected. Let $M$ be the set of maximal elements of $P$. Then, let $$ \begin{align} P_1&=\{p\in P\mid \forall m\in M:p\le m\} \\ P_2&=P\setminus P_1 \end{align} $$ That is, $P_1$ is the set of common descendents of $M$, and $P_2$ is everything else.

I claim that $P=P_1+P_2$. That is, everything in $P_1$ is less than everything in $P_2$. To prove this, let $x\in P_1$ and $y\in P_2$ be arbitrary. If $y\in M$, it is obvious that $x\le y$, so assume $y\notin M$. There must exist $m_1\in M$ such that $y\le m_1$ (by considering the longest chain containing $y$). Furthermore, since $y\in P_2$, there exists $m_2\in M$ such that $y\not\le m_2$. Since $x\in P_1$, we have both $x\le m_1$ and $x\le m_2$. Since $m_1$ and $m_2$ are maximal, we have $m_1\not\le m_2$ and $m_1\not\ge m_2$. Since $\{x,y,m_1,m_2\}$ is not isomorphic to $Z_4$, it must be the case that either $x\ge y$ or $x\le y$. You can rule out the case $x\ge y$, so we do conclude $x\le y$, therefore proving $P=P_1+P_2$.

Since $P=P_1+P_2$, and by induction we know that $P_1$ and $P_2$ are series-parallel, we conclude that $P$ is series-parallel.