In this paper we consider the class of interval orders, recently considered by several authors from both an algebraic and an enumerative point of view. According to Fishburn’s Theorem (Fishburn J Math Psychol 7:144–149, 1970), these objects can be characterized as posets avoiding the poset 2 + 2. We provide a recursive method for the unique generation of interval orders of size n + 1 from those of size n, extending the technique presented by El-Zahar (1989) and then re-obtain the enumeration of this class, as done in Bousquet-Melou et al. (2010). As a consequence we provide a method for the enumeration of several subclasses of interval orders, namely AV(2 + 2, N), AV(2 + 2, 3 + 1), AV(2 + 2, N, 3 + 1). In particular, we prove that the first two classes are enumerated by the sequence of Catalan numbers, and we establish a bijection between the two classes, based on the cardinalities of the principal ideals of the posets.

Generation and Enumeration of Some Classes of Interval Orders / Filippo Disanto; Elisa Pergola; Renzo Pinzani; Simone Rinaldi. - In: ORDER. - ISSN 0167-8094. - STAMPA. - 30:(2013), pp. 663-676. [10.1007/s11083-012-9269-x]

Generation and Enumeration of Some Classes of Interval Orders

PERGOLA, ELISA;PINZANI, RENZO;
2013

Abstract

In this paper we consider the class of interval orders, recently considered by several authors from both an algebraic and an enumerative point of view. According to Fishburn’s Theorem (Fishburn J Math Psychol 7:144–149, 1970), these objects can be characterized as posets avoiding the poset 2 + 2. We provide a recursive method for the unique generation of interval orders of size n + 1 from those of size n, extending the technique presented by El-Zahar (1989) and then re-obtain the enumeration of this class, as done in Bousquet-Melou et al. (2010). As a consequence we provide a method for the enumeration of several subclasses of interval orders, namely AV(2 + 2, N), AV(2 + 2, 3 + 1), AV(2 + 2, N, 3 + 1). In particular, we prove that the first two classes are enumerated by the sequence of Catalan numbers, and we establish a bijection between the two classes, based on the cardinalities of the principal ideals of the posets.
2013
30
663
676
Filippo Disanto; Elisa Pergola; Renzo Pinzani; Simone Rinaldi
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/818076
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact