is Íslenska en English

Lokaverkefni (Meistara)

Háskólinn í Reykjavík > Tæknisvið / School of Technology > MSc Tölvunarfræðideild / Department of Computer Science >

Vinsamlegast notið þetta auðkenni þegar þið vitnið til verksins eða tengið í það: https://hdl.handle.net/1946/25589

Titill: 
  • Titill er á ensku Equivalence classes of mesh patterns with a dominating pattern
  • Jafngildisflokkar möskvamynstra með ríkjandi mynstri
Námsstig: 
  • Meistara
Útdráttur: 
  • Útdráttur er á ensku

    A permutation is an arrangement of n objects. Sets of permutations classified by the avoidance of classical permutation patterns capture many interesting properties, such as stack-sortability, and have links to many different combinatorial objects. Mesh patterns are an extension of classical patterns that allow additional restrictions to be placed on occurrences of the pattern. Two mesh patterns are coincident if they are avoided by the same set of permutations. We provide sufficient conditions for coincidence among mesh patterns, whilst also avoiding a longer classical pattern. These conditions, along with two special cases, are used to completely classify coincidence amongst families containing a mesh pattern of length 2 and a classical pattern of length 3.
    Two patterns are Wilf-equivalent if they have the same number of avoiders at every length, we completely Wilf-classify mesh patterns of length 2 when avoiding the classical pattern 231. Finally we attempt to show some non-trivial Wilf-equivalences between avoiders of sets of the form 231, m1 and 321, m2, as well as discussing possible future work that could be derived from this work.

  • Umröðun er endurröðun á n hlutum. Mengi umraðana sem forðast klassísk umr- aðanamynstur geta lýst mörgum áhugaverðum eiginleikum, s.s. staflaraðanlegum umröðunum, og tengjast mörgum fléttufræðilegum hugtökum. Möskvamynstur eru útvíkkun á klassískum mynsturum sem leyfa auka skorður á tilvik mynstursins. Tvö möskvamynstur eru samtilfallandi ef sömu umraðanir forðast hvert um sig. Við finnum nægjanleg skilyrði fyrir því að tvö möskvamynstur séu samtilfallandi, þegar umraðanir forðast einnig lengra klassískt mynstur. Þessi skilyrði, ásamt tveimur sértilfellum, eru notuð til að gera greiningu á hvaða pör af möskvamynstri af lengd 2 og klassísku mynstri af lengd 3 eru samtilfallandi.
    Tvö mynstur eru Wilf-jafngild ef jafn margar umraðanir af hverri lengd forðast hvert mynstur um sig. Við Wilf-flokkum öll pör sem innihalda möskvamynstur af lengd 2 og klassíska mynstrið 231. Að lokum finnum við ófáfengileg Wilf-jafngildi milli pars 231, m1 og 321, m2, ásamt því fjalla um vinnu sem má byggja á þessari ritgerð.

Samþykkt: 
  • 7.7.2016
URI: 
  • http://hdl.handle.net/1946/25589


Skrár
Skráarnafn Stærð AðgangurLýsingSkráartegund 
msc-tannock-2016.pdf386,08 kBOpinnHeildartextiPDFSkoða/Opna