Tight Lower Bound for Pattern Avoidance Schur-Positivity

MaRDI QIDQ6414657zbMATH OpenFDO

Authors Avichai Marmor

Publication date 21 October 2022

Abstract: For a set of permutations (patterns) $Pi$ 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 $kge4$, the size of such $Pi$ must be at least $3$ unless $Pisubseteq[1,2,dots,k],;[k,dots,1]$, and asked for a general lower bound. We prove that the minimal size of such $Pi$ is exactly $k-1$. The proof applies a new generalization of a theorem of Bose from extremal combinatorics. This generalization is proved using the multilinear polynomial approach of Alon, Babai and Suzuki to the extension by Ray-Chaudhuri and Wilson to Bose's theorem.

This page was built for publication: Tight Lower Bound for Pattern Avoidance Schur-Positivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6414657)