Monday, July 22, 2013

Forbidden induced suborders

Several classes of partial orders can be described by their avoidance of a single induced suborder:
  • Antichains: [1 1]
  • Total orders: [2]
  • Weak orders: {1 1, [1 1] 1}
  • Upper/lower forests: [1 2] and [2 1]
  • Interval orders: {[1 1] 2}
  • Series-parallel partial orders: the zigzag poset
The semiorders can be described as the subset of the set of interval orders that avoid another order type in addition to the one the interval orders avoid.

No comments:

Post a Comment