On naturally labelled posets and permutations avoiding 12–34

Tools

Bevan, David and Cheon, Gi-Sang and Kitaev, Sergey (2025) On naturally labelled posets and permutations avoiding 12–34. European Journal of Combinatorics, 126. 104117. ISSN 0195-6698 (https://doi.org/10.1016/j.ejc.2024.104117)

[thumbnail of Bevan-etal-EJC-2025-naturally-labelled-posets-and-permutations-avoiding-12-34]
Preview
 Text. Filename: Bevan-etal-EJC-2025-naturally-labelled-posets-and-permutations-avoiding-12-34.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo
Download (1MB)| Preview

Abstract

A partial order ≺ on [n] is naturally labelled (NL) if x ≺ y implies x < y. We establish a bijection between {3, 2+2}-free NL posets and 12–34-avoiding permutations, determine functional equations satisfied by their generating function, and use series analysis to investigate their asymptotic growth, presenting evidence of stretched exponential behaviour. We also exhibit bijections between 3-free NL posets and various other objects, and determine their generating function. The connection between our results and a hierarchy of combinatorial objects related to interval orders is described.

ORCID iDs

Bevan, David ORCID logoORCID: https://orcid.org/0000-0001-7179-2285, Cheon, Gi-Sang and Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647;
CORE (COnnecting REpositories)