Coincidences and Growth of Boxed Mesh Patterns
Abstract
A boxed mesh pattern is a mesh pattern whose selected entries lie in an empty axis-parallel rectangle. We classify coincidences of boxed patterns with classical and vincular patterns, exhibit a genuinely bivincular coincidence, and prove that no boxed--bivincular coincidence occurs for patterns of length at least five. Together with known results, this shows that every boxed pattern of length at least five has factorial growth and hence fails the Stanley--Wilf property. At length four, one exceptional orbit is enumerated by the semi-Baxter numbers, while the remaining exceptional orbit, {2143,3412}, is unresolved; we conjecture that it has factorial growth. For Box(123), we derive an exact maximum-insertion identity and prove the subfactorial upper bound 25nnβn, where β=log2(2cos(π/7))<0.85. A closed enumeration remains open. We also prove a general first-moment formula for boxed mesh patterns that depends only on the length of the underlying pattern; in particular, the expected number of Box(123) occurrences in a uniformly random permutation of length n is asymptotic to nlog n. For Box(12), we identify the occurrence statistic with the up-degree in the strong Bruhat order, obtaining its maximum, its mean, and an exact insertion identity for the distribution polynomials. We conjecture that the coefficients of these polynomials are unimodal.
Related
- Equidistribution of mesh patterns of length 2 on involutions
- Distributions of Mesh Patterns of Short Lengths on Separable Permutations
- On mesh patterns of short length: Equidistribution and enumeration
- Seven Coincidences and Sixty Symmetries
- Symbol sequences from three-rotor coincidences and their word-complexity
BibTeX
@misc{kitaev2026coincidences,
title = {{Coincidences and Growth of Boxed Mesh Patterns}},
author = {Sergey Kitaev and Dun Qiu and Chao Xu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.13764},
eprint = {2609.13764},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.13764},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Coincidences and Growth of Boxed Mesh Patterns
AU - Sergey Kitaev
AU - Dun Qiu
AU - Chao Xu
PY - 2026
DA - 2026/09/12
PB - arXiv
DO - 10.48550/arxiv.2609.13764
UR - https://arxiv.org/abs/2609.13764
AB - A boxed mesh pattern is a mesh pattern whose selected entries lie in an empty axis-parallel rectangle. We classify coincidences of boxed patterns with classical and vincular patterns, exhibit a genuinely bivincular coincidence, and prove that no boxed--bivincular coincidence occurs for patterns of length at least five. Together with known results, this shows that every boxed pattern of length at least five has factorial growth and hence fails the Stanley--Wilf property. At length four, one exceptional orbit is enumerated by the semi-Baxter numbers, while the remaining exceptional orbit, {2143,3412}, is unresolved; we conjecture that it has factorial growth. For Box(123), we derive an exact maximum-insertion identity and prove the subfactorial upper bound 2^5nn^βn, where β=log_2(2cos(π/7))<0.85. A closed enumeration remains open. We also prove a general first-moment formula for boxed mesh patterns that depends only on the length of the underlying pattern; in particular, the expected number of Box(123) occurrences in a uniformly random permutation of length n is asymptotic to nlog n. For Box(12), we identify the occurrence statistic with the up-degree in the strong Bruhat order, obtaining its maximum, its mean, and an exact insertion identity for the distribution polynomials. We conjecture that the coefficients of these polynomials are unimodal.
ER -