Wilf-classification of mesh patterns of short length

Abstract

This B.Sc. project deals with mesh pattern avoidance in permutations. A mesh pattern is a pair P=(p,R), where p is a permutation of length k and R is a subset of [0,k]x[0,k]. The elements of R denote filled boxes in a mesh pattern. For a permutation u to contain a mesh pattern, it has to contain the underlying classical pattern p, and no points in u can be located in the shaded boxes. In this paper we begin the study of Wilf-classifying mesh patterns by classifying 776 out of the 1024 mesh patterns of length 2. Two mesh patterns P and Q are said to be equivalent if for any permutation u, u avoids P if and only if u avoids Q. The paper introduces a new operation that preserves pattern equivalence and provides rules determining which additional boxes in a mesh pattern P can be shaded. This is useful to lower the number of patterns one needs to look at in the process of Wilf-classifying patterns. We also have some observations on the only non-trivial interval pattern of length 3.

Í þessu B.Sc. verkefni vinnum við með mynstraforðun möskvamynstra í umröðunum. Möskvamynstur er par P=(p,R) þar sem p er umröðun af lengd k og R er hlutmengi í [0,k]x[0,k]. Stökin í R tákna skyggða ferninga í möskvamynstrinu. Umröðun u er sögð innihalda möskvamynstrið P ef hún inniheldur grunnmynstrið p og engir punktar u eru inn í skyggðu ferningum mynstursins P. Í þessu verkefni hefjum við Wilf-flokkun möskvamynstra, þar með hafa 776 mynstur af 1024 verið Wilf-flokkuð. Tvö möskvamynstur P og Q eru sögð vera jafngild ef fyrir sérhverja umröðun u gildir að u forðast P ef og aðeins ef u forðast Q. Verkefnið kynnir nýja aðgerð sem varðveitir jafngildi mynstra og gefur reglur um hvaða ferninga í mynstri P má skyggja aukalega í möskvamynstri. Þessi aðgerð er hentug til að minnka fjölda þeirra mynstra sem þarf að skoða við Wilf-flokkun mynstra. Einnig höfum við skoðað eina bilamynstrið af lengd 3 sem er ekki augljóst, og setjum fram athugasemdir um það.