Seminar Details
How Prolific is a Random Permutation?
- Start Date: February 24, 2020
- Event Start Time: 2:00 PM
- Event End Time: 3:00 PM
- Seminar Series: Rutgers Discrete Mathematics Seminar
- Presenter(s): Peter Winkler - Dartmouth College
- Event Location: Hill Center-Room 705
- Presentation Type: Stand Alone Presentation
- Abstract:
A "pattern" of length k in a permutation P in S_n is a permutation in S_k determined by choosing k elements from {1,2,...,n} and looking at the order of their images under P. For example, if P_3 > P_5 then the positions 3 and 5 produce the pattern 21.
P is "d-prolific" if every pattern of length n-d is different; equivalently, the set of patterns of P of length n-d has size n choose d.
We show that the probability that a uniformly random P in S_n is d-prolific tends to e^{-d^2-d} as n grows.
Joint work with Simon Blackburn and Cheyne Homberger.