Monday November 19, 2001

Speaker: Ira Gessel

Title: Longest increasing subsequences: algorithms and applications

Abstract: Given a finite sequence, such as 1 4 2 5 3 8 6, deleting any of the entries leaves a subsequence, for example, 1 2 5 8. This subsequence is increasing, and it is in fact a longest increasing subsequence of the original sequence (though it is not the only longest increasing subsequence). The problem of finding the longest increasing subsequence of a sequence is interesing algorithmically, and has surprisingly deep mathematical ramifications. The most straightforward approach to the problem is through dynamic programming, but a modification discovered by Craige Schensted (and later rediscovered by Edsger Dijkstra) is slightly more efficient and has many remarkable properties. Algorithmically, it also solves the problem of finding the largest union of k increasing subsequences, and mathematically it has numerous applications, notably in enumerative combinatorics and in representation theory.

This will be a very basic talk, and should be comprehensible to undergraduates in both mathematics and in computer science.