Fixed-pattern containment conjecture at the universality threshold

Let Sk\mathcal{S}_k denote the permutations of [k][k]. Fix ε>0\varepsilon>0 and set n=(1+ε)k2/4n=(1+\varepsilon)k^2/4. For πSk\pi\in\mathcal{S}_k, let σ\sigma be a uniformly random permutation of length nn. Fixed-pattern containment conjecture. With high probability, σ\sigma contains π\pi. The statement is a weakening of Alon's universality conjecture because it fixes one pattern rather than requiring simultaneous containment of every pattern in Sk\mathcal{S}_k. The source explicitly describes it as an apparently open problem.

Sources & referencesView supporting material

Primary source

Xiaoyu He and Matthew Kwan, “Universality of random permutations”, arXiv:1911.12878 (2020).

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.