Albert's conjecture on pattern-avoiding subsequence expectations

From papers

Let XX be a finite proper subset of j2Sj\bigcup_{j\geq 2}\mathfrak{S}_j, meaning that XX does not contain both an identity permutation 12j12\cdots j and a reverse identity permutation k21k\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

limnsn(X)1/n=14(limnEX(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.

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

No solutions have been posted yet.