On pattern-avoidance and symmetry

Seminar
Speaker
Avichai Marmor (Bar-Ilan University)
Date
12/06/2022 - 15:30 - 14:10Add to Calendar 2022-06-12 14:10:00 2022-06-12 15:30:00 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.   Room 216/201 and also Zoom אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Room 216/201 and also Zoom
Abstract

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.
 

Last Updated Date : 08/06/2022