Asymptotic monotonicity conjecture for pattern-avoiding ordered set partitions

About 14 years old · traced to

Let SmS_m be the symmetric group on mm letters, let ρ∈Sm\rho\in S_m be a permutation, and let op⁡n,k(ρ)\operatorname{op}_{n,k}(\rho) denote the number of ordered set partitions of [n][n] into kk blocks that avoid ρ\rho. For each fixed kk, let n0(k)n_0(k) be a threshold depending only on kk. Asymptotic monotonicity conjecture. For each fixed kk, there exists n0(k)n_0(k) such that for each ρ∈Sm\rho\in S_m and n≥n0(k)n\ge n_0(k),

op⁡n,k+1(ρ)>op⁡n,k(ρ)>⋯>op⁡n,∣ρ∣(ρ).\operatorname{op}_{n,k+1}(\rho)>\operatorname{op}_{n,k}(\rho)>\cdots>\operatorname{op}_{n,\lvert\rho\rvert}(\rho).

The conjecture proposes eventual monotonicity in the number of blocks, beginning at k+1k+1 and continuing down to the pattern length. The source states that this conjecture was first proved by Marcus and Tardos, so it is recorded as solved.

References

Primary source

Anant Godbole, Adam Goyt, Jennifer Herdan and Lara Pudwell, “Pattern Avoidance in Ordered Set Partitions”, arXiv:1212.2530 (2013).

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.