Rutgers Discrete Mathematics Seminar

Title: Permutation Pattern Densities

Speaker: Peter Winkler, Dartmouth College

Date: Monday, November 28, 2016 2:00 pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ


The "pattern density" of a permutation pi in a permutation sigma is the fraction of subsequences of sigma (written in one-line form) that are ordered like pi. For example, the density of the pattern "12" in sigma is the number of pairs i < j with sigma(i) < sigma(j), divided by n choose 2. What does a typical permutation look like that has one or more pattern densities fixed? To help answer this we employ limit objects called "permutons," together with a variational principle that identifies the permuton that best represents a given class of permutations. Joint work with Rick Kenyon, Dan Kral' and Charles Radin.