Topology Seminar, Ann Trenk (Wellesley): 'Unit Interval Orders of Open and Closed Intervals'

Wednesday, March 25, 2015
4:15 PM - 5:30 PM (ET)
ESC 638
Event Type
Karen Collins,, x2169

Abstract: The class of unit interval orders arises in scheduling problems and has a lovely forbidden poset characterization. The characterization remains the same whether the intervals used in the representation are all open intervals or all closed intervals. In this talk we consider the class of posets that arise when both open and closed unit intervals are allowed in the same representation. We give a structural characterization of this class of posets and an efficient algorithm for recognizing the class. The algorithm takes a poset P as input and either produces a representation or returns a forbidden poset induced in P.

Get Directions
Event Date
Event Time