Seminar

To participate in this seminar, please register HERE.

For uniformly random permutations of length n, it is well known that the length of the longest increasing subsequence is very close to 2 \sqrt{n}. More generally, the Schensted shape of the permutation (under Schensted insertion) rescaled by 1/\sqrt{n} converges to a certain non-random limit shape and described by Vershik--Kerov and Logan--Shepp. When looking at a sequence of numbers which claims to be "pseudo-random", one could ask whether the longest increasing subsequence and the Schensted shape have similar limits. For most pseudo-random sequences, I do not know the answer to this question so there will be some open questions posed. For the sequence consisting of the fractional parts of multiples of an irrational number, the answer is "no", and I will discuss joint work with T. Kyle Petersen which explores the behavior of the Schensted shape, which can be described explicitly in terms arithmetic properties of the irrational number which generates the sequence.

Longest Increasing Subsequence and the Schensted Shape of Some Pseudo-Random Sequences 12.1 MB application/pdf

Longest Increasing Subsequence And The Schensted Shape Of Some Pseudo-Random Sequences