*Title: Interval orders and a hierarchy of combinatorial structures related to them
*Speaker: Sergey Kitaev (University of Strathclyde, UK)
*Place / Date : AORC Seminar Room / Sep. 15, 2017 (Fri) pm 3:30 - 4:30
*Abstract:
A partially ordered set (poset) is an interval order if it is isomorphic to some set of intervals on the real line ordered by left-to-right precedence. Interval orders are important in mathematics, computer science, engineering and the social sciences. For example, complex manufacturing processes are often broken into a series of tasks, each with a specified starting and ending time. Some of the tasks are not time-overlapping, so at the completion of the first task, all resources associated with that task can be used for the following task. On the other hand, if two tasks have overlapping time periods, they compete for resources and thus can be viewed as conflicting tasks.
A poset is said to be (2+2)-free if no two disjoint 2-element chains have comparable elements. In 1970, Fishburn proved that (2+2)-free posets are precisely interval orders. In 2010, Bousquet-Mélou, Claesson, Dukes, and Kitaev introduced ascent sequences, which not only allowed to enumerate interval orders, but also to connect them to other combinatorial objects, namely to Stoimenow's matchings, to certain upper triangular matrices, and to certain pattern avoiding permutations (a very active area of research these days). A host of papers by various authors have followed this initial paper.
In this talk, I will review some of results from these papers and will discuss a hierarchy of
combinatorial structures related to interval orders.