Wilf-classification of mesh patterns of short length

Electronic Journal of Combinatorics, Volume 22 (2015)

Isak, Ingibjorg, Steinunn, Henning and Lína

The goal of this paper is to Wilf-classify mesh patterns of length 2. To this end we prove The Shading Lemma, which gives sufficient conditions for two mesh patterns to be coincident (i.e., avoided by the same permutations) and therefore Wilf-equivalent. The lemma, along with other rules which implie Wilf-coincidence we show that there are at most 56 Wilf-classes of mesh patterns of length 2. We conjecture that the exact number is 46 and hope to revisit this area and prove this conjecture.

Download the paper

• Electronic Journal of Combinatorics, Volume 22 (2015)
• arXiv (Same as journal version except for a minor modification in the paragraph under Table 1, p. 11)
• BSc thesis of the students

Presentations

• Wilf classification of mesh patterns of short length, BSC thesis presentation, Reykjavik University, May 2011

Additional Material

• Wilf-flokkun möskvamynstra, an Icelandic article in Verpill, the magazine of mathematics and physics students at University of Iceland

Later work (last updated 3 October 2026)

• A. Claesson, B. E. Tenner and H. Úlfarsson, Coincidence among families of mesh patterns, Australas. J. Combin. 63 (2015). Necessary conditions for two mesh patterns to be coincident, and a generalization of the Shading Lemma.
• M. Tannock and H. Úlfarsson, Equivalence classes of mesh patterns with a dominating pattern, Discrete Math. Theor. Comput. Sci. 19 (2018). Coincidences and Wilf-equivalences of mesh patterns inside a classical pattern class, including a complete Wilf-classification of the mesh patterns of length 2 inside the 231-avoiding permutations.
• S. Kitaev and P. B. Zhang, Distributions of mesh patterns of short lengths, Adv. Appl. Math. 110 (2019). The first systematic study of the distributions of these patterns. Among other results, it proves that the patterns 48 and 49, 55 and 56, and 63, 64 and 65 of this paper are equidistributed, and therefore Wilf-equivalent, settling some of the conjectures in Tables 11 and 12.
• S. Kitaev, P. B. Zhang and X. Zhang, Distributions of several infinite families of mesh patterns, Appl. Math. Comput. 372 (2020). Distribution and avoidance formulas for infinite families of mesh patterns, generalizing earlier results including some from this paper.
• B. Han and J. Zeng, Equidistributions of mesh patterns of length two and Kitaev and Zhang’s conjectures, Adv. Appl. Math. 127 (2021). Proves more equidistributions of mesh patterns of length 2, including four conjectures of Kitaev and Zhang.
• C. Bean, B. Gudmundsson, T. K. Magnússon and H. Úlfarsson, Algorithmic coincidence classification of mesh patterns, Inform. and Comput. 292 (2023). Strengthens the Shading Lemma with forces, and completes the coincidence classification of mesh patterns of length at most 3, automatically except for one case.
• X. Su, S. Kitaev and J. Zhang, Equidistribution of mesh patterns of short length, preprint (2026). Lowers the upper bound on the number of Wilf-classes of mesh patterns of length 2 from this paper’s 56 to 49.
• Q. Fang, S. Fu, S. Kitaev, H.-J. Li, X. Su and Z.-Y. Sun, On mesh patterns of short length: equidistribution and enumeration, preprint (2026). Lowers the bound to 47, leaving a single open equivalence.
• Z.-R. Zhang and H. Zhao, The last distribution-equivalence class of mesh patterns of length 2, preprint (2026). Proves that last equivalence, completing the classification: there are exactly 46 Wilf-classes of mesh patterns of length 2, as conjectured in this paper.
• S. Kitaev, D. Qiu and C. Xu, Coincidences and growth of boxed mesh patterns, preprint (2026). Proves that the boxed pattern Box(2413) and the vincular pattern 2-41-3 have the same avoiders, and explains why the Shading Lemma cannot be applied directly: the two shadings are not nested.
• All citing papers on Google Scholar (47)