Asymptotic monotonicity conjecture for pattern-avoiding ordered set partitions

Let SmS_m be the symmetric group on mm letters, let ρSm\rho\in S_m be a permutation, and let opn,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 nn0(k)n\ge n_0(k),

opn,k+1(ρ)>opn,k(ρ)>>opn,ρ(ρ).\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.

Sources & referencesView supporting material

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.