Albert's conjecture on pattern-avoiding subsequence expectations
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Richard P. Stanley, “Increasing and Decreasing Subsequences of Permutations and Their Variants”, arXiv:math/0512035 (2005).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.