Decomposing labeled interval orders as pairs of permutations
type: Item
instance of: scholarly article
title: Decomposing labeled interval orders as pairs of permutations
zbMATH Open document ID: 1298.05023
author: Anders Claesson
author: Stuart A. Hannah
published in: The Electronic Journal of Combinatorics
publication date: 2014-10-23T00:00:00Z
full work available at URL: https://arxiv.org/abs/1405.2441
full work available at URL: v21i4p16
review text: Summary: 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.
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05A19
zbMATH DE Number: 6360691
zbMATH Keywords: ballot matrix
zbMATH Keywords: composition matrix
zbMATH Keywords: sign reversing involution
zbMATH Keywords: interval order
zbMATH Keywords: \(2+2\)-free poset
zbMATH Keywords: Fishburn
zbMATH Keywords: ascent bottom
MaRDI profile type: Publication
arXiv ID: 1405.2441
cites work: Q4375247
cites work: An obvious proof of Fishburn's interval order theorem
cites work: (2+2)-free posets, ascent sequences and pattern avoiding permutations
cites work: Partition and composition matrices
cites work: Composition matrices, \((2+2)\)-free posets and their specializations
cites work: Intransitive indifference with unequal indifference intervals
cites work: Q5377443
cites work: Fishburn diagrams, Fishburn numbers and their refined generating functions
cites work: On a conjecture about enumerating \((2+2)\)-free posets
cites work: Vassiliev invariants and a strange identity related to the Dedekind eta-function
Recommended article: Interval posets of permutations
Recommended article: Decompositions of partially ordered sets
Recommended article: Decomposing Random Permutations into Order-Isomorphic Subpermutations
Recommended article: Partially ordered sets associated with permutations
Recommended article: Labelled well-quasi-order for permutation classes
Recommended article: Q4694426
Recommended article: A separation decomposition for orders
Recommended article: Q4943008
Recommended article: Decomposition of partial orders
Recommended article: Combinatorial aspects of interval orders and interval graphs
description: scientific article; zbMATH DE number 6360691