Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Department Colloquium

Sergey Kitaev

Univ Strathclyde

Interval orders and related combinatorial objects.

Abstract:

A poset is called (2+2)-free if it does not contain an induced subposet that is isomorphic to the union of two disjoint 2-element chains. In 1970, Fishburn proved that (2+2)-free posets are in one-to-one correspondence with intensively studied interval orders. Recently, Bousquet-Melou et al. (M. Bousquet-Melou, A. Claesson, M. Dukes, and S. Kitaev, (2+2)-free posets, ascent sequences and pattern avoiding permutations, J. Combin. Theory Ser. A 117 (2010) 884-909.) invented so-called ascent sequences which not only allowed to enumerate (2+2)-free posets (and thus interval orders), but also to connect them to other combinatorial objects, namely to Stoimenow's diagrams (also called regular linearized chord diagrams which were used to study the space of Vassiliev's knot invariants), to certain upper triangular matrices, and to certain pattern avoiding permutations (a very popular area of research these days). Several other papers appeared following the influential work by Bousquet-Melou et al. Among other results, two conjectures, of Pudwell and Jovovic, were solved while dealing with (2+2)-free posets and ascent sequences. In my talk, I will overview relevant results and research directions.

Host: Jeff Remmel

February 16, 2012

3:00 PM

AP&M 6402

****************************