Albert's conjecture on pattern-avoiding subsequence expectations

At least 20 years old · documented by

Let XX be a finite proper subset of ⋃j≥2Sj\bigcup_{j\geq 2}\mathfrak{S}_j, meaning that XX does not contain both an identity permutation 12⋯j12\cdots j and a reverse identity permutation k⋯21k\cdots 21. Let sn(X)s_n(X) be the number of permutations in Sn\mathfrak{S}_n avoiding every pattern in XX, and let EX(n)E_X(n) be the expected length of the longest subsequence avoiding every pattern in XX in a uniformly random permutation of Sn\mathfrak{S}_n. Albert's conjecture. If XX is proper, then

lim⁡n→∞sn(X)1/n=14(lim⁡n→∞EX(n)n)2.\lim_{n\to\infty}s_n(X)^{1/n}=\frac{1}{4}\left(\lim_{n\to\infty}\frac{E_X(n)}{\sqrt{n}}\right)^2.

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

Never refreshed

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.