A Tutte polynomial for partially ordered sets
We investigate the Tutte polynomial of a greedoid associated to a partially ordered set. In this case, we explore the deletion-contraction formula in two ways and develop an antichain expansion for the polynomial. We show that the polynomial can determine the number of order ideals, order filters and antichains of all sizes of a poset \(P\), but neither the number of chains, multichains, extensions, nor the dimension of \(P\). We show how to compute the polynomial for the direct sum, ordinal sum and ordinal product of two posets, but show this cannot be done for the direct product. We also show it is possible to determine \(f(P^*)\) from \(f(P)\), where \(P^*\) is the dual poset of \(P\). We also consider the idea of feasible isomorphism of two greedoids and show that two feasibly isomorphic greedoids have the same polynomial.
scientific article; zbMATH DE number 562389
scientific article