On pattern-avoidance and symmetry

For a set $\Pi$ of permutations (patterns) in $S_k$, consider the set of all permutations in $S_n$ that avoid all patterns in $\Pi$.  An important problem in current algebraic combinatorics is to find pattern sets $\Pi$ such that the corresponding quasi-symmetric function is symmetric for all $n$.  Recently, Bloom and Sagan proved that for any $k \ge 4$, the size of such $\Pi$ must be at least $3$ (with one exception), and asked for a general bound.

In this talk, we prove that the minimal size of such $\Pi$ is exactly $k - 1$.  The proof uses a new variant of a theorem of Ray-Chaudhuri and Wilson in extremal combinatorics.  This variant is proved using the polynomial approach of Alon, Babai and Suzuki to the original theorem.

No prior knowledge will be assumed.

This work is a part of an MSc Thesis, supervised by Ron Adin and Yuval Roichman.