PreprintCC BY 4.0arXiv
Short permutation pattern waves: The complete length-five classification
Abstract
For a permutation pi in Sk, a pi-wave is an increasing sequence of integers whose consecutive gaps have relative order pi. Let g(pi, n) be the maximum cardinality of a pi-wave-free subset of [n], and let P(pi, r) be the least integer N such that every r-coloring of [N] contains a monochromatic pi-wave. We determine the asymptotic orders of both functions for every permutation of length at most five. Existing upper bounds and weak-wave constructions provide sharp bounds for all but eight length-five patterns in S_5. For these eight exceptional alternating patterns, we establish g(pi, n) = Theta((log n)squared) and P(pi, r) = Theta(r(log r)squared).
Related
- A complete classification of permutation binomials of the form Xr(Xq−1+a) over finite fields
- Word Length and Diameter in Permutation Groups
- Characterization of a class of complete permutation quadrinomials over 𝔽22m
- A Complete Dichotomy for L∞ Permutation Removal
- Involutions avoiding 4321 and another pattern of length four
BibTeX
@misc{qiu2026short,
title = {{Short permutation pattern waves: The complete length-five classification}},
author = {Lihong Qiu and Minglei Mao and Yaping Mao},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.04184},
eprint = {2611.04184},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.04184},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Short permutation pattern waves: The complete length-five classification
AU - Lihong Qiu
AU - Minglei Mao
AU - Yaping Mao
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.04184
UR - https://arxiv.org/abs/2611.04184
AB - For a permutation pi in Sk, a pi-wave is an increasing sequence of integers whose consecutive gaps have relative order pi. Let g(pi, n) be the maximum cardinality of a pi-wave-free subset of [n], and let P(pi, r) be the least integer N such that every r-coloring of [N] contains a monochromatic pi-wave. We determine the asymptotic orders of both functions for every permutation of length at most five. Existing upper bounds and weak-wave constructions provide sharp bounds for all but eight length-five patterns in S_5. For these eight exceptional alternating patterns, we establish g(pi, n) = Theta((log n)squared) and P(pi, r) = Theta(r(log r)squared).
ER -