Rutgers Discrete Mathematics Seminar

Title: Indecomposability Threshold for Random Permutations

Speaker: Huseyin Acan, Rutgers University

Date: Monday, November 9, 2015 2:00 pm

Location: Hill center, room 425, Rutgers University, Busch Campus, Piscataway, NJ


A permutation of n is indecomposable if no proper initial segment is a permutation of an integer less than n. Consider a permutation a(n,m) chosen uniformly at random from the set of permutations of n with exactly m inversions. This permutation is decomposable for small m and indecomposable for large m (with probability approaching 1 as n tends to infinity). I will talk about a threshold m(n) around which the transition from 'being decomposable' to 'being indecomposable' occurs and also the number of indecomposable components a(n,m) when m is slightly below the threshold.

Joint work with Boris Pittel.