is Íslenska en English

Lokaverkefni (Bakkalár)

Háskóli Íslands > Verkfræði- og náttúruvísindasvið > B.S. verkefni - Verkfræði- og náttúruvísindasvið >

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

Titill: 
  • Titill er á ensku Occurrence graphs of patterns in permutations
Námsstig: 
  • Bakkalár
Efnisorð: 
Útdráttur: 
  • Útdráttur er á ensku

    This paper is based on a generalization of the idea behind the proof of the Simultaneous Shading Lemma by Claesson et al. (2014). We define the occurrence graph G_p(\pi) of a pattern p in a permutation \pi as the graph with the occurrences of p in \pi as vertices and edges between the vertices if the occurrences differ by exactly one element. We study the general properties of the occurrence graphs and some interesting extreme cases. The main theorem in this paper is that every hereditary property of graphs produces a permutation class.

  • Þessi grein er byggð á útvíkkun á hugmyndinni sem notuð var í sönnuninni á skyggingarhjálparsetningunni í Claesson et at. (2014). Við skilgreinum tilvikanet, G_p(\pi), fyrir mynstur p í umröðun \pi sem net með hnút fyrir hvert tilvik p í \pi og leggi milli hnúta hvers samsvarandi tilvik eru eins fyrir utan eitt stak. Við rannsökum almenna eiginleika þessara tilvikaneta og áhugaverð jaðartilvik. Meginsetning greinarinnar er að sérhver arfgengur eiginleiki neta leiðir til umraðanaklasa.

Tengd vefslóð: 
Samþykkt: 
  • 11.6.2015
URI: 
  • http://hdl.handle.net/1946/22017


Skrár
Skráarnafn Stærð AðgangurLýsingSkráartegund 
HI-BSc-thesis_Occurrence-graphs.pdf514.05 kBOpinnHeildartextiPDFSkoða/Opna