Málstofa í stærðfræði

Fyrirlesarar: Bjarni Jens Kristinsson, Háskóla Íslands, og Henning Úlfarsson, Háskólanum í Reykjavík
Titill: Occurrence graphs of patterns in permutations

Staðsetning: Naustið, Endurmenntun (hér)
Tími: Fimmtudagur 4. júní, klukkan 15:00-16:00.

Ágrip:

This paper is based on a generalisation 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.