On naturally labelled posets and permutations avoiding 12–34

David Bevan, Gi-Sang Cheon, Sergey Kitaev

Research output: Contribution to journalArticlepeer-review

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.
Original languageEnglish
Article number104117
Number of pages18
JournalEuropean Journal of Combinatorics
Volume126
Early online date13 Jan 2025
DOIs
Publication statusE-pub ahead of print - 13 Jan 2025

Keywords

  • naturally labelled poset
  • pattern avoidance
  • bijective combinatorics
  • generating function
  • asymptotic series analysis
  • stretched exponential

Fingerprint

Dive into the research topics of 'On naturally labelled posets and permutations avoiding 12–34'. Together they form a unique fingerprint.

Cite this