***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Colin Defant, Princeton

Thursday 6th December, 3:00 in Fine Hall 224.

Title: Structure in stack-sorting

The study of permutation patterns began with Knuth’s analysis of a certain 
“stack-sorting algorithm” in 1968. In his 1990 PhD. thesis, West investigated 
a deterministic variant of Knuth’s algorithm, which we can view as a function 
s that defines a dynamical system on the set of permutations. He defined the 
fertility of a permutation to be the number of preimages of that permutation 
under s. We will describe a colorful method for computing the fertility of 
any permutation, answering a question of Bousquet-Mélou.

Applications of this method allow us to reprove and generalize several known
theorems and improve the best known upper bound for the number of so-called
“t-stack-sortable” permutations of length n when t=3 and when t=4. The method
also allows us to connect the stack-sorting map with free probability theory,
set partitions, acyclic orientations of graphs, lattice paths, and several
well-studied sequences. Finally, we will consider two operators on words that
extend the stack-sorting map.

		----------------------------------

Next week: Tuesday Guangming Jing; Thursday Sebastian Cioaba.

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)