On symmetric pattern avoidance sets

Tuong Le · 2026

Read On symmetric pattern avoidance sets by Tuong Le (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-07195.txt.

Description

A 2026 arXiv research paper by Tuong Le. For a set of permutations S ⊆ S n S\subseteq S_{n} , consider the quasisymmetric generating function Q ⁡ ( S ) := ∑ w ∈ S F n , Des ⁡ ( w ) , Q(S):=\sum_{w\in S}F_{n,\Des(w)}, where Des ⁡ ( w ) := { i ∣ w ⁡ ( i ) > w ⁡ ( i + 1 ) } \Des(w):=\{i\mid w(i)>w(i+1)\} is the descent set of w w and F n , Des ⁡ ( w ) F_{n,\Des(w)} is

Catalog record

CREATORTuong Le
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE98 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-07195

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On symmetric pattern avoidance sets Tuong Le Abstract . For a set of permutations S ⊆ S n S\subseteq S_{n} , consider the quasisymmetric generating function Q ⁡ ( S ) := ∑ w ∈ S F n , Des ⁡ ( w ) , Q(S):=\sum_{w\in S}F_{n,\Des(w)}, where Des ⁡ ( w ) := { i ∣ w ⁡ ( i ) > w ⁡ ( i + 1 ) } \Des(w):=\{i\mid w(i)>w(i+1)\} is the descent set of w w and F n , Des ⁡ ( w ) F_{n,\Des(w)} is Gessel’s fundamental quasisymmetric function. A set of permutations is said to be symmetric (respectively, Schur-positive) if its quasisymmetric generating function is symmetric (respectively, Schur-positive). Given a set Π \Pi of permutations, let S n ​ ( Π ) S_{n}(\Pi) denote the set of permutations in S n S_{n} that avoid all patterns in Π . \Pi. A set Π \Pi is said to be symmetrically avoided (respectively, Schur-positively avoided) if S n ​ ( Π ) S_{n}(\Pi) is symmetric (respectively, Schur-positive) for all n . n. Marmor proved in 2025 that for n ≥ 5 n\geq 5 , a symmetric set S ⊆ S n S\subseteq S_{n} has size at least n − 1 n-1 unless S ⊆ { 12 ⋯ n , n ⋯ 21 } S\subseteq\{12\cdots n,n\cdots 21\} and asked for a general classification of the possible sizes of symmetric sets not containing the monotone elements 12 ⋯ n 12\cdots n and n ⋯ 21 n\cdots 21 . We give a complete answer to this question for n ≥ 52 . n\geq 52. We also give a classification of symmetric sets of size at most n − 1 n-1 , thereby showing that they are actually Schur-positive, resolving a conjecture of Marmor. Finally, we give a classification of symmetrically avoided sets of size at most n − 1 n-1 , thereby showing that they are actually Schur-positively avoided. 1. Introduction For a set of permutations S\subseteq S_{n} , consider the quasisymmetric generating function (1.1) Q(S):=\sum_{w\in S}F_{n,\Des(w)}, where \Des(w):=\{i\mid w(i)>w(i+1)\} is the descent set of w and F_{n,\Des(w)} is Gessel’s fundamental quasisymmetric function (see Section 2.2 for more definitions and background). Gessel’s fundamental quasisymmetric functions were first introduced by Gessel in 1984 [ 6 ] , and the problem of finding sets of permutations for which the associated quasisymmetric function is symmetric was first posed by Gessel and Reutenauer in 1993 [ 5 ] . We say a set S is symmetric if Q(S) is symmetric, and S is Schur-positive if Q(S) is Schur-positive. It is natural to ask for a classification of the possible sizes of symmetric sets. It turns out (Remark 4.1 ) that S is symmetric if and only if S\setminus\{\iota_{n},\delta_{n}\} is, where \iota_{n}:=12\dots n and \delta_{n}:=n\dots 21 are the monotone elements. Thus, it suffices to ask for the possible sizes of a symmetric set without the monotone elements (see, e.g., [ 8 , Question 5.3] ). Marmor [ 8 ] showed in 2025 that for n\geq 5 , if S\subseteq S_{n} is symmetric and S\not\subseteq\{\iota_{n},\delta_{n}\} then |S|\geq n-1. In this paper, we classify all the possible sizes of a symmetric set without monotone elements in S_{n} for n\geq 52. It turns out that S is symmetric if and only if S_{n}\setminus(S\cup\{\iota_{n},\delta_{n}\}) is (Remark 4.2 ), so it suffices to classify all the possible sizes up to \frac{n!-2}{2}. The classification follows from the following two theorems. Theorem 1.1 . For n\geq 4 and (n-1)(n-3)\leq p\leq\frac{n!-2}{2}, there is a symmetric set of size p without monotone elements. Theorem 1.2 . For n\geq 52 and p<(n-1)(n-3) , there exists a symmetric set of size p without monotone elements if and only if ( exactly ) one of the following is true (1) p=qn-r for some 0\leq r\leq q<n-3, (2) n is even and p=\frac{n(n-3)}{2}+c(n-1) for some c\geq 0, (3) n is odd and p=\binom{n-1}{2}+cn for some c\geq 0. Marmor showed that their lower bound n-1 is tight by giving an example of a Schur-positive set of size exactly n-1 , and conjectured that all symmetric sets realizing this lower bound are actually Schur-positive [ 8 , Conjecture 5.2] . We give a classification of symmetric sets of sizes at most n-1 , which gives a new proof of Marmor’s result and show that all symmetric sets of size at most n-1 are Schur-positive. Theorem 1.3 . Suppose S\subseteq S_{n} and |S|\leq n-1 . Then the following are equivalent: (1) S is symmetric. (2) One of the following is true: (a) S\subseteq\{\iota_{n},\delta_{n}\}. (b) S=\{\pi_{1},\dots,\pi_{n-1}\} where either \Des(\pi_{i})=\{i\} for all i , or \Des(\pi_{i})=[n-1]\setminus\{i\} for all i . (c) n=4 and S=\{\pi_{1},\pi_{2}\} or S=\{\pi_{1},\pi_{2},\iota_{4}\} or S=\{\pi_{1},\pi_{2},\delta_{4}\} , where \Des(\pi_{1})=\{1,3\} and \Des(\pi_{2})=\{2\} . (d) n=6 and S=\{\pi_{1},\pi_{2},\dots,\pi_{5}\} where \Des(\pi_{1})=\{1,3,5\}, \Des(\pi_{2})=\{2,5\}, \Des(\pi_{3})=\{3\},\Des(\pi_{4})=\{1,4\},\Des(\pi_{5})=\{2,4\} ; or \Des(\pi_{1})=\{2,4\}, \Des(\pi_{2}) =\{1,3,4\} , \Des(\pi_{3})=\{1,2,4,5\}, \Des(\pi_{4})=\{2,3,5\}, \Des(\pi_{5})=\{1,3,5\} . (3) S is Schur-positive. A remarkable example of a symmetric set of permutations is the arc permutations [ 3 ] , which is the set of all permutations in S_{n} avoiding the pattern set \Pi:=\{w\in S_{4}\mid|w(1)-w(2)|=2\}. This has motivated a line of work in finding sets of patterns \Pi such that S_{n}(\Pi) , the set of all permutations in S_{n} avoiding \Pi , is symmetric for all n [ 2 , 4 , 7 , 8 , 9 ] . Such sets are called symmetrically avoided . If S_{n}(\Pi) is actually Schur-positive for all n , we say \Pi is Schur-positively avoided . Bloom and Sagan [ 2 ] initiated the study of symmetrically avoided sets of small size. They proved that for k\geq 4, if \Pi\subseteq S_{k} is symmetrically avoided and |\Pi|\leq 2, then \Pi\subseteq\{\iota_{k},\delta_{k}\}. Marmor [ 8 ] extended this result, showing that for k\geq 5 , if \Pi\subseteq S_{k} is symmetrically avoided and |\Pi|\not\subseteq\{\iota_{k},\delta_{k}\}, then |\Pi|\geq k-1. We give a complete classification of all symmetrically avoided sets of size at most k-1, which as a corollary shows that these sets are actually Schur-positively avoided. Theorem 1.4 . Given \Pi\subseteq S_{k} such that |\Pi|\leq k-1 , the following are equivalent. (1) \Pi is symmetrically avoided, (2) \Pi is a partial shuffle or the complement of a partial shuffle, or \Pi\subseteq\{\iota_{k},\delta_{k}\}, (3) \Pi is Schur-positively avoided. Here, the word “complement” refers to the element-wise complement of a set, which we define in Section 2 (Definition 2.21 ). Partial shuffles were defined by Bloom and Sagan [ 2 ] ; we recap this in Definition 5.8 . Our proof technique involves recasting the problem of symmetric sets in terms of harmonic set systems , which we define in Section 3 (Definition 3.13 ). Informally, a harmonic set system is a collection of sets such that the sizes of their intersections are uniform in a certain sense. Inspired by [ 8 ] , for each set of permutations one can define an associated set system, which we prove is harmonic if and only if the set of permutation is symmetric. The rest of the paper is structured as follows. In Section 2 we go over relevant background and preliminaries. In Section 3 , we introduce harmonic set systems. In Section 4 , we prove Theorem 1.1 and Theorem 1.2 . In Section 5 , we prove Theorem 1.3 and Theorem

Read the complete text