On the Complexity of Partial Order Properties

The recognition complexity of ordered set properties is considered in terms of how many questions must be put to an adversary to decide if an unknown partial order has the prescribed property. We prove a lower bound of order n2 for properties that are characterized by forbidden substructures of fixed size. For the properties being connected, and having exactly k comparable pairs, k � n2/4 we show that the recognition complexity is (n 2). The complexity of interval orders is exactly (n 2) - 1. We further establish bounds for being a lattice, being of height k and having width k.