Tight lower bound for pattern avoidance and symmetric functions

Abstract For a set of permutations (patterns) Π in S k , consider the set of permutations in S n that avoid all patterns in Π. In current algebraic combinatorics, a significant problem is to identify pattern sets Π for which the corresponding quasisymmetric function is symmetric for all n . Recently, Bloom and Sagan proved that unless Π ⊆ {12 … k , k … 21}, the size of such Π must be at least 3 for any k ≥ 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 Π 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.