Albert's conjecture on pattern-avoiding subsequence expectations
Let be a finite proper subset of , meaning that does not contain both an identity permutation and a reverse identity permutation . Let be the number of permutations in avoiding every pattern in , and let be the expected length of the longest subsequence avoiding every pattern in in a uniformly random permutation of . Albert's conjecture. If is proper, then
The limit on the left exists, whereas the existence of the limit on the right is part of the conjecture. The result would relate the exponential growth rate of a pattern-avoidance class to the asymptotic scale of its longest avoiding subsequences.
References
Primary source
Richard P. Stanley, “Increasing and Decreasing Subsequences of Permutations and Their Variants”, arXiv:math/0512035 (2005).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.