Tight Lower Bound for Pattern Avoidance and Symmetric Functions

Abstract

For a set of permutations (patterns) $\Pi$ in $S_k$, consider the set of permutations in $S_n$ that avoid all patterns in $\Pi$. In current algebraic combinatorics, a significant problem is to identify pattern sets $\Pi$ for which the corresponding quasisymmetric function is symmetric for all $n$. Recently, Bloom and Sagan proved that unless $\Pi \subseteq \{12\dots k,k\dots 21\}$, the size of such $\Pi$ must be at least $3$ for any $k\ge 4$. They also posed a general lower bound conjecture. In this work, we resolve this conjecture and give a tight lower bound, namely, the minimal size of such $\Pi$ is exactly $k-1$. The proof relies on a novel generalization of Bose's theorem in extremal combinatorics, utilizing the multilinear polynomial approach introduced by Alon, Babai, and Suzuki.