The strict ordering of non-one-block patterns

At least 10 years old · documented by

Let Πk\Pi_k be the set of partitions of [k][k], let βk∈Πk\beta_k\in\Pi_k be the partition with one block, and let Πn(τ)\Pi_n(\tau) denote the set of partitions of [n][n] avoiding τ\tau. Define τ≺π\tau\prec\pi when ∣Πn(τ)∣≤∣Πn(π)∣|\Pi_n(\tau)|\leq |\Pi_n(\pi)| for all n>kn>k, with strict inequality for all sufficiently large nn.

Strict ordering conjecture. If k≥4k\geq 4, τ∈Πk\tau\in\Pi_k, and τ≠βk\tau\neq\beta_k, then

τ≺βk\tau\prec\beta_k

and

∣Πn(τ)∣<∣Πn(βk)∣|\Pi_n(\tau)|<|\Pi_n(\beta_k)|

for all n>kn>k.

Computer evidence suggests this ordering, while the paper proves it for patterns with exactly two blocks; the assertion for all other patterns remains conjectural in the supplied text.

References

Primary source

Jonathan Bloom and Dan Saracino, “Pattern avoidance for set partitions à la Klazar”, arXiv:1511.00192 (2016).

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.