Printable PDF
Department of Mathematics,
University of California San Diego

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

Special Combinatorics Seminar

Mitchel T. Keller

London School of Economics and Political Science

Asymptotic Enumeration of Labelled Interval Orders

Abstract:

In his 1985 monograph Interval Orders and Interval Graphs, Fishburn noted the dearth of enumerative results for interval orders and labelled semiorders, standing in contrast to the well-understood case of interval graphs and unlabelled semiorders. (The latter are enumerated by the Catalan numbers.) Recently, work by Bousquet-Mélou et al. linked certain integer sequences termed ascent sequences to unlabelled interval orders. This allowed for an asymptotic enumeration of unlabelled interval orders through earlier work by Zagier involving the same generating function that enumerates ascent sequences. Building on subsequent work by Khamis, this talk develops an asymptotic enumeration of the labelled interval orders on an $n$-element set. This is joint work with Graham Brightwell (LSE).

Host: Jeff Remmel

May 3, 2012

4:00 PM

AP&M 7321

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