Monday, November 26, 2018 at 4:00pm to 5:00pm
Irani Hall (RRI), 101
1050 Childs Way, Los Angeles, CA 90089
(Reception, Irrani Hall Foyer: 3:30pm-4:00pm)
Emeritus Professor of Mathematics, MIT
An increasing subsequence of a permutation a_1, a_2, ... , a_n of 1,2, ... , n is a subsequence b_1,b_2, ... , b_k satisfying b_1 < b_2 < ... < b_k, and similarly for decreasing subsequence. The earliest result in this area is due to Erdös and Szekeres in 1935: any permutation of 1,2, ... , pq + 1 has an increasing subsequence of length p+1 or a decreasing subsequence of length q+1. This result turns out to be closely connected to the RSK algorithm from the representation theory of the symmetric group. A lot of work has been devoted to the length k of the longest increasing subsequence of a permutation 1,2, ... , n, beginning with Ulam's question of determining the average value of this number over all such permutations. There are many interesting analogues of longest increasing subsequences, such as longest alternating subsequences, i.e., subsequences b_1,b_2, ... , b_k of a permutation a_1, a_2, ... , an satisfying b_1>b_2<b_3>b_4< ... . We will survey these highlights of the remarkable theory of increasing and decreasing subsequences.
Richard Stanley is Professor Emeritus of Mathematics, MIT, since January 2018. He received the B.S. in mathematics from Caltech in 1966, and the Ph.D. in mathematics from Harvard University in 1971, under the direction of Gian-Carlo Rota. He joined the MIT faculty in applied mathematics in 1973, and became a professor in 1979. Professor Stanley's research concerns problems in algebraic combinatorics. Professor Stanley's distinctions include the SIAM George Pólya Prize in applied combinatorics, 1975, a Guggenheim fellowship, 1983, the Leroy P. Steele Prize for Mathematical Exposition, 2001, the Rolf Schock Prize in Mathematics, 2003, and the Aisenstadt Chair, University of Montreal, 2007. Stanley was the inaugural holder of the Department's Levinson Professorship Chair of Mathematics, 2000-2010. He was appointed Senior Scholar at the Clay Mathematics Institute in 2004, and received the Honorary Doctor from the University of Waterloo. In 2007, he received an Honorary Professorship from Nankai University. He is a Fellow of the American Academy of Arts & Sciences (1988) and Member of the National Academy of Sciences (1995).