"Permutation patterns and the Möbius function"

Einar Steingrímsson
Reykjavik University

Monday, April 26, 2010
4:00 pm
845 POT

Abstract:

The letters 2,6,4 in the permutation 5271643 form the pattern 132, because they appear in the same order of size as 132, that is, smallest letter first, then the largest letter and the middle one last. As another example, an occurrence of the pattern 1234 in a permutation is simply an increasing subsequence of length 4, and 5271634 avoids this pattern, that is, has no occurrence of it. Patterns in permutations have been much studied in the last few decades, and they turn out to be connected to many different combinatorial objects and various other fields, such as theoretical computer science, statistical mechanics and algebraic geometry.

The set of all permutations (of integers 1,2,...,n for any n) forms a partially ordered set, where the order relation is pattern containment. For example, 132 is smaller than 5271643 in this poset, whereas 1234 is not.

An inevitable question for any poset is what the Möbius function on its intervals is. For the patten poset, this seems to be hard for generic intervals. On the other hand, there is a computationally effective solution for the so-called separable permutations, and several results for other special cases. There are also many open problems and conjectures, and untouched aspects such as the topological properties of intervals in this poset. In short, this seems to be an interesting landscape that is only beginning to be explored.

I will report on joint work with Bridget Tenner and with Vít Jelínek, Eva Jelínková and Alex Burstein.