### 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.