Series-parallel posets and the Tutte polynomial (Q1815311)

Let \(P\) a poset and let \(I \subseteq P\). Then \(I\) is an order ideal if whenever \(x\in I\) and \(x>y\), then \(y\in I\). For \(S \subseteq P\), define the rank of \(S\), denoted \(r_p(S)\) (or simply \(r(S))\) as follows: \[ r_p (S)= \max_{I \subseteq S} \bigl\{|I |: I \text{ is an order ideal} \bigr\}. \] The Tutte polynomial of \(P\) is defined by \[ f(P; t,z) = \sum_{S \subseteq P} t^{|P|-r(S)} z^{|S |-r(S)}. \] The scope of this paper is to study the Tutte polynomial \(f(P;t,z)\) of a series-parallel partially ordered set \(P\). The author shows that \(f(P)\) can be computed in polynomial time when \(P\) is series-parallel and that series-parallel posets having isomorphic deletions and contractions are themselves isomorphic. A formula for \(f(P^*)\) in terms of \(f(P)\) is obtained and shows that these two polynomials factor over \(Z[t,z]\) in the same way. Also, the author examines several subclasses of the class of series-parallel posets, proving that \(f(P)\neq f(Q)\) for non-isomorphic \(P\) and \(Q\) in the largest of these classes.