On naturally labelled posets and permutations avoiding 12–34

David Bevan; Gi-Sang Cheon; Sergey Kitaev

doi:10.1016/j.ejc.2024.104117

On naturally labelled posets and permutations avoiding 12–34

David Bevan, Gi-Sang Cheon, Sergey Kitaev

Mathematics And Statistics

Research output: Contribution to journal › Article › peer-review

89 Downloads (Pure)

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 language	English
Article number	104117
Number of pages	18
Journal	European Journal of Combinatorics
Volume	126
Early online date	13 Jan 2025
DOIs	https://doi.org/10.1016/j.ejc.2024.104117
Publication status	Published - 31 May 2025

Funding

The second author was partially supported by National Research Foundation of Korea (NRF) grants funded by the Korean government (MSIP) 2016R1A5A1008055 and 2019R1A2C1007518.

Keywords

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

Access to Document

10.1016/j.ejc.2024.104117Licence: CC BY 4.0

Bevan-etal-EJC-2025-naturally-labelled-posets-and-permutations-avoiding-12-34Final published version, 1.24 MBLicence: CC BY 4.0

Cite this

@article{76777ebcd57441f390a022eec91ef3a7,

title = "On naturally labelled posets and permutations avoiding 12–34",

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.",

keywords = "naturally labelled poset, pattern avoidance, bijective combinatorics, generating function, asymptotic series analysis, stretched exponential",

author = "David Bevan and Gi-Sang Cheon and Sergey Kitaev",

year = "2025",

month = may,

day = "31",

doi = "10.1016/j.ejc.2024.104117",

language = "English",

volume = "126",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

}

TY - JOUR

T1 - On naturally labelled posets and permutations avoiding 12–34

AU - Bevan, David

AU - Cheon, Gi-Sang

AU - Kitaev, Sergey

PY - 2025/5/31

Y1 - 2025/5/31

N2 - 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.

AB - 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.

KW - naturally labelled poset

KW - pattern avoidance

KW - bijective combinatorics

KW - generating function

KW - asymptotic series analysis

KW - stretched exponential

UR - https://arxiv.org/abs/2311.08023

U2 - 10.1016/j.ejc.2024.104117

DO - 10.1016/j.ejc.2024.104117

M3 - Article

SN - 0195-6698

VL - 126

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

M1 - 104117

ER -

On naturally labelled posets and permutations avoiding 12–34

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this