Scholarlink

<p>For a set of permutations (patterns) Π in <i>S</i><sub><i>k</i></sub>, consider the set of permutations in <i>S</i><sub><i>n</i></sub> 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 <i>n</i>. Recently, Bloom and Sagan proved that unless Π ⊆ {12 … <i>k</i>, <i>k</i> … 21}, the size of such Π must be at least 3 for any <i>k</i> ≥ 4. They also posed a general lower bound conjecture.</p><p>In this work, we resolve this conjecture and give a tight lower bound, namely, the minimal size of such Π is exactly <i>k</i> − 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Tight lower bound for pattern avoidance and symmetric functions

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年6月29日

查看全文
  • Avichai Marmor

摘要

For a set of permutations (patterns) Π in Sk, consider the set of permutations in Sn 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.