Myers' asymptotic monotone-subsequence conjecture

About 12 years old · traced to

Let kk be a positive integer. For a permutation τ\tau of [n]={1,…,n}[n]=\{1,\dots,n\}, let mk(τ)m_k(\tau) denote the number of monotone subsequences of length k+1k+1. Myers' asymptotic conjecture. As n→∞n\to\infty, every permutation of [n][n] has at least

(1+o(1))1kk(nk+1)(1+o(1))\frac{1}{k^k}\binom{n}{k+1}

monotone subsequences of length k+1k+1. This is a weaker asymptotic form of Myers' exact minimum conjecture, and it remains open in the generality stated.

References

Primary source

József Balogh, Ping Hu, Bernard Lidický, Oleg Pikhurko, Balázs Udvari and Jan Volec, “Minimum number of monotone subsequences of length 4 in permutations”, arXiv:1411.3024 (2014).

Additional references

2 papers in this index state this conjecture (2014). The statement above is taken from the most recent of them; the others are arXiv:1405.6894.

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.