Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: Sorting with Restricted Containers
Speaker: Vince Vatter, University of Florida
Date: Thursday, April 27, 2017 5:00pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
Restricted containers are a new data structure generalizing stacks, queues, and deques. I will describe how this viewpoint rapidly leads to functional equations for the classes of sortable permutations. These functional equations can sometimes be solved by the kernel method, but, much more easily, by the computer via guessing and checking.
I will also present several general results about the rationality, algebraicity, and the existence of Wilfian formulas for certain classes of permutations sortable by restricted containers and present several examples of relatively small permutation classes which, although we can generate thousands of terms of their enumerations via this viewpoint, appear to not have D-finite generating functions.
This is joint work with Michael Albert, Cheyne Homberger, Jay Pantone, and Nathaniel Shar.