Whiteman Memorial Mathematics Lectures Joint with CAMS Distinguished Lecture: Increasing and decreasing subsequences

Monday, November 26, 2018 at 4:00pm to 5:00pm

This is a past event.

Irani Hall (RRI), 101
1050 Childs Way, Los Angeles, CA 90089

(Reception, Irrani Hall Foyer: 3:30pm-4:00pm)

Richard Stanley
Emeritus Professor of Mathematics, MIT

Short abstract:
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).

 

 

Event Type

Lecture / Talk / Workshop

Campus

University Park Campus

Department
Mathematics
Add this to your calendar

Recent Activity