11:30am-noon: Q&A with Henning Úlfarsson (Reykjavik University)
Moderator: Luca Ferrari
(This is 9:30am US Pacific, 12:30 US Eastern, 4:30pm GMT, 5:30pm in the UK, 6:30pm CEST, 7:30pm in Israel, 12:30am in China, 2:30am in Sydney, 4:30am in New Zealand)
Title: Algorithmic solutions to problems in permutation patterns
Abstract: The field of permutation patterns arguably arises out of Knuth’s answer to “Which permutations are sortable by a single pass through a stack?” We will take that as our starting point and see how a question about the stack-sorting algorithm can be solved by another algorithm, which generalizes to describing permutations whose image under stack-sort belong to a permutation class. This leads us to mesh patterns and an algorithm that can describe arbitrary sets of permutations in terms of avoided mesh patterns. Redundancy in the output of this algorithm leads to natural questions about when two mesh patterns describe the same set of permutations. (Did you know that a permutation has a descent if and only if it has an inversion?). There is, of course, an algorithm that can help us with this question.
Being able to describe a set of permutations in terms of avoided mesh patterns is satisfying, but often sheds no light on the enumeration question: How many permutations of each length are there in the set I am looking at? There are other algorithms for answering this question. One of these as been the main focus of my group for several years now, and we will end with showing how it can, hopefully, merge many of the threads described above into a unified framework.
This keynote address is available here.
Back to the Workshop Program