Discrete CATS Seminar
U N I V E R S I T Y
K E N T U C K Y
WHERE CATS =
845 PATTERSON OFFICE TOWER
"Permutation patterns and the Möbius function"
Monday, April 26, 2010
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
I will report on joint work with Bridget Tenner and with
Eva Jelínková and Alex Burstein.