论文标题
紧密的下限以避免模式的schur积极性
Tight Lower Bound for Pattern Avoidance Schur-Positivity
论文作者
论文摘要
对于$ s_k $中的一组排列（模式）$π$，请考虑$ s_n $中所有排列的集合，以避免$π$中的所有模式。当前代数组合学的一个重要问题是找到图案集$π$，使得相应的准合成功能对于所有$ n $都是对称的。最近，Bloom和Sagan证明，对于任何$ k \ ge 4 $，除非$π$的大小至少为$ 3 $，除非$π\ subseteq \ {[[1，2，\ dots，k]，\; [k，\ dots，1] \} $，并要求使用一般的下限。 我们证明，这种$π$的最小尺寸正好是$ k -1 $。该证明应用了从极端组合学的BOSE定理的新概括。使用Alon，Babai和Suzuki的多项式多项式方法证明了这种概括，Ray-Chaudhuri和Wilson延伸到Bose定理。
For a set of permutations (patterns) $Π$ in $S_k$, consider the set of all permutations in $S_n$ that avoid all patterns in $Π$. An important problem in current algebraic combinatorics is to find pattern sets $Π$ 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 $Π$ must be at least $3$ unless $Π\subseteq \{[1, 2, \dots, k],\; [k, \dots, 1]\}$, and asked for a general lower bound. We prove that the minimal size of such $Π$ 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.
