Decomposing labeled interval orders as pairs of permutations

Anders Claesson, Stuart Alexander Hannah

Research output: Contribution to journal › Article

48 Downloads (Pure)

Abstract

We introduce ballot matrices, a signed combinatorial structure whose definition naturally follows from the generating function for labeled interval orders. A sign reversing involution on ballot matrices is defined. We show that matrices fixed under this involution are in bijection with labeled interval orders and that they decompose to a pair consisting of a permutation and an inversion table. To fully classify such pairs, results pertaining to the enumeration of permutations having a given set of ascent bottoms are given. This allows for a new formula for the number of labeled interval orders.
Original languageEnglish
Article numberP4.16
Number of pages20
JournalThe Electronic Journal of Combinatorics
Volume21
Issue number4
Publication statusPublished - 16 Oct 2014

Fingerprint

Interval Order
Permutation
Involution
Ascent
Signed
Bijection
Enumeration
Generating Function
Table
Inversion
Classify
Decompose

Keywords

  • ballot matrix
  • composition matrix
  • sign reversing involution
  • interval order
  • 2+2-free posset
  • ascent bottom

Cite this

Claesson, Anders ; Hannah, Stuart Alexander. / Decomposing labeled interval orders as pairs of permutations. In: The Electronic Journal of Combinatorics. 2014 ; Vol. 21, No. 4.
@article{358f85cc08b9465b82cb8339f577522b,
title = "Decomposing labeled interval orders as pairs of permutations",
abstract = "We introduce ballot matrices, a signed combinatorial structure whose definition naturally follows from the generating function for labeled interval orders. A sign reversing involution on ballot matrices is defined. We show that matrices fixed under this involution are in bijection with labeled interval orders and that they decompose to a pair consisting of a permutation and an inversion table. To fully classify such pairs, results pertaining to the enumeration of permutations having a given set of ascent bottoms are given. This allows for a new formula for the number of labeled interval orders.",
keywords = "ballot matrix, composition matrix, sign reversing involution, interval order, 2+2-free posset, ascent bottom",
author = "Anders Claesson and Hannah, {Stuart Alexander}",
year = "2014",
month = "10",
day = "16",
language = "English",
volume = "21",
journal = "The Electronic Journal of Combinatorics",
issn = "1077-8926",
number = "4",

}

Claesson, A & Hannah, SA 2014, 'Decomposing labeled interval orders as pairs of permutations', The Electronic Journal of Combinatorics, vol. 21, no. 4, P4.16.

Decomposing labeled interval orders as pairs of permutations. / Claesson, Anders; Hannah, Stuart Alexander.

In: The Electronic Journal of Combinatorics, Vol. 21, No. 4, P4.16, 16.10.2014.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Decomposing labeled interval orders as pairs of permutations

AU - Claesson, Anders

AU - Hannah, Stuart Alexander

PY - 2014/10/16

Y1 - 2014/10/16

N2 - We introduce ballot matrices, a signed combinatorial structure whose definition naturally follows from the generating function for labeled interval orders. A sign reversing involution on ballot matrices is defined. We show that matrices fixed under this involution are in bijection with labeled interval orders and that they decompose to a pair consisting of a permutation and an inversion table. To fully classify such pairs, results pertaining to the enumeration of permutations having a given set of ascent bottoms are given. This allows for a new formula for the number of labeled interval orders.

AB - We introduce ballot matrices, a signed combinatorial structure whose definition naturally follows from the generating function for labeled interval orders. A sign reversing involution on ballot matrices is defined. We show that matrices fixed under this involution are in bijection with labeled interval orders and that they decompose to a pair consisting of a permutation and an inversion table. To fully classify such pairs, results pertaining to the enumeration of permutations having a given set of ascent bottoms are given. This allows for a new formula for the number of labeled interval orders.

KW - ballot matrix

KW - composition matrix

KW - sign reversing involution

KW - interval order

KW - 2+2-free posset

KW - ascent bottom

UR - http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p16

M3 - Article

VL - 21

JO - The Electronic Journal of Combinatorics

JF - The Electronic Journal of Combinatorics

SN - 1077-8926

IS - 4

M1 - P4.16

ER -

Claesson A, Hannah SA. Decomposing labeled interval orders as pairs of permutations. The Electronic Journal of Combinatorics. 2014 Oct 16;21(4). P4.16.

Access to Document