Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department |
Algorithms, Combinatorics and Optimization Seminar
For more information, please visit the home page for the program in Algorithms, Combinatorics and Optimization at Carnegie Mellon University. Carnegie Mellon University offers an interdisciplinary Ph.D program in Algorithms, Combinatorics and Optimization. This program is the first of its kind in the United States. It is administered jointly by the Tepper School of Business (Operations Research group), the Computer Science Department (Algorithms and Complexity group) and the Department of Mathematical Sciences (Discrete Mathematics group). (Learn more...) Nayantara Bhatnagar University of Delaware Title: Lengths of Monotone Subsequences in a Mallows Permutation Abstract: The longest increasing subsequence (LIS) of a uniformly random permutation is a well studied problem. Vershik–Kerov and Logan–Shepp first showed that asymptotically the typical length of the LIS is 2√n . This line of research culminated in the work of Baik–Deift–Johansson who related this length to the Tracy–Widom distribution.We study the length of the LIS and LDS of random permutations drawn from the Mallows measure, introduced by Mallows in connection with ranking problems in statistics. Under this measure, the probability of a permutation q^{Inv(p)} where q is a real parameter and Inv(p) is the number of inversions in p. We determine the typical order of magnitude of the LIS and LDS, large deviation bounds for these lengths and a law of large numbers for the LIS for various regimes of the parameter q.This is joint work with Ron Peled. |