Colloquium: Henning Ulfarsson (University of Reykjavik)

When:
April 10, 2015 @ 3:30 pm – 4:30 pm
2015-04-10T15:30:00-10:00
2015-04-10T16:30:00-10:00
Where:
Keller 401

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)