Speaker: Henning Ulfarsson (University of Reykjavik)
Title: Pattern avoiding permutations and non-crossing subgraphs of polygons
Abstract: We will explain a surprising connection between independent sets arising from the study of permutations avoiding the pattern 132 and the classical problem of enumerating non-crossing subgraphs in a complete graph drawn on a regular polygon. This leads to a generalization of n-gons, where some internal edges have been doubled. These can be used to count subclasses of permutations avoiding the pattern 1324, the only principal permutation class of length 4 that remains unenumerated. No prior knowledge on permutation patterns is assumed. Joint work with Christian Bean and Murray Tannock (also at Reykjavik University)