Seminar Event Detail


Student Combinatorics

Date:  Tuesday, December 01, 2020
Location:  Virtual (5:00 PM to 6:00 PM)

Title:  The RSK algorithm for longest paths

Abstract:   The Robinson-Schensted-Knuth correspondence gives a very concrete algorithm for converting a permutation into a pair of Young Tableaux, from which we can extract the longest increasing subsequence of the original permutation. Fulton and Viennot's Geometric construction gives a different algorithm for producing these Young Tableaux, without so many intermediate steps. Along the way, it converts longest increasing subsequence(s) into disjoint longest paths in N^2 (the positive integer lattice). We will go over this alternative algorithm, enjoy some of its symmetries, and (time permitting) discuss how we might recover these longest disjoint paths.

Files:


Speaker:  Scott Neville
Institution: 

Event Organizer:     

 

Edit this event (login required).
Add new event (login required).
For access requests and instructions, contact math-webmaster@umich.edu

Back to previous page
Back to UM Math seminars/events page.