[:is]Málstofa í stærðfræði
Fyrirlesari: Giulio Cerbai, University of Florence
Titill: Sorting Permutations Using Pattern-Avoiding Stacks
Staðsetning: Tg-227
Tími: Fimmtudagur 9. maí kl. 11.40
Ágrip:
The problem of sorting a permutation using a stack was proposed by Knuth in the 1960s. As it is well known, sortable permutations can be characterized in terms of pattern avoidance and their enumeration is given by the Catalan numbers. Since then, lots of generalizations have been proposed, either by increasing the number of stacks or by using different sorting devices (queues, pop stacks…). Unfortunately, the same problem with 2 stack in series is too hard and both the characterization and the enumeration of the sortable permutations are still unknown.
In this work we start the analysis of a new sorting device, consisting in two restricted stacks in series, where each stack cannot contain a given pattern. We will use a right-greedy procedure, thus generalizing the case of the 2-West sortable permutations. Our goal is to provide the first results in this new framework, hoping to gain a better understanding of the general 2-stacksort problem. [:en]
Math Colloquium
Speaker: Giulio Cerbai, University of Florence
Title: Sorting Permutations Using Pattern-Avoiding Stacks
Location: Tg-227
Time: Thursday May 9 at 11.40 am
Abstract:
The problem of sorting a permutation using a stack was proposed by Knuth in the 1960s. As it is well known, sortable permutations can be characterized in terms of pattern avoidance and their enumeration is given by the Catalan numbers. Since then, lots of generalizations have been proposed, either by increasing the number of stacks or by using different sorting devices (queues, pop stacks…). Unfortunately, the same problem with 2 stack in series is too hard and both the characterization and the enumeration of the sortable permutations are still unknown.
In this work we start the analysis of a new sorting device, consisting in two restricted stacks in series, where each stack cannot contain a given pattern. We will use a right-greedy procedure, thus generalizing the case of the 2-West sortable permutations. Our goal is to provide the first results in this new framework, hoping to gain a better understanding of the general 2-stacksort problem. [:]