Forest Polynomials and Pattern Avoidance Annie Guo, Dora Woodruff Abstract Forest polynomials, recently introduced by Nadeau and Tewari, can be thought of as a quasisymmetric analogue for Schubert polynomials. They have already been shown to exhibit interesting interactions with Schubert polynomials; for example, Schubert polynomials decompose positively into forest polynomials. We further describe this relationship by showing that a Schubert polynomial 𝔖 w \mathfrak{S}_{w} is a forest polynomial exactly when w w avoids a set of 6 6 patterns. This result adds to the long list of properties of Schubert polynomials that are controlled by pattern avoidance. 1 Introduction Forest polynomials, first introduced by Nadeau and Tewari in their study of the permutahedral variety [ 9 ] , are a quasisymmetric analogue for Schubert polynomials. They form a linear basis for a quasisymmetric variant of the coinvariant algebra [ 9 ] , represent cohomology classes for a quasisymmetric variant of the flag variety [ 2 ] , and have rich combinatorial properties, many of which parallel the combinatorial properties of Schubert polynomials (for example, see [ 8 ] ). Forest polynomials and Schubert polynomials also interact with each other in interesting ways. For instance, Nadeau and Tewari showed that Schubert polynomials decompose positively into forest polynomials [ 9 ] , and pipe dream-like models have been developed for forest polynomials [ 8 ] . Given this, it is natural to ask: when do these two classes of polynomials coincide? One would hope for the answer to this question to be expressible in terms of pattern avoidance . Indeed, pattern avoidance controls many combinatorial and algebraic properties of Schubert polynomials. For example, a Schubert polynomial \mathfrak{S}_{w} is a flagged Schur polynomial if and only if w avoids 2143 [ 7 ] , it is a standard elementary monomial if and only if w avoids 312 and 1432 [ 11 ] , and its coefficients are all 0 or 1 if and only if w avoids a list of 12 patterns [ 4 ] . Much work has also been dedicated to bounding the principal specialization of \mathfrak{S}_{w} in terms of pattern counts in w (for example, see [ 10 ] or [ 6 ] ). Along these lines, our main result is that the intersection between Schubert polynomials and forest polynomials is also controlled by pattern avoidance: Theorem 1.1 . A Schubert polynomial \mathfrak{S}_{w} is also a forest polynomial if and only if w avoids the following set of patterns: \{1432,2413,2431,14523,32154,341265\} There is a second interpretation of this result worth mentioning. When they introduced forest polynomials in [ 9 ] , Nadeau and Tewari defined \Omega -equivalence, an equivalence relation on the set of reduced words of a given permutation. To each equivalence class \mathcal{C} , they attach a corresponding forest polynomial \mathfrak{F}(\mathcal{C}) . Theorem 1.2 . if \mathcal{G}_{w} denotes the set of \Omega -equivalence classes of the reduced words of w^{-1} , then: \mathfrak{S}_{w}=\sum_{\mathcal{C}\in\mathcal{G}_{w}}\mathfrak{F}(\mathcal{C}) Therefore, asking which Schubert polynomials are forest polynomials is equivalent to asking which permutations w have exactly one \Omega -equivalence class. 1.1 Organization In section 2 , we will go over the combinatorial model for forest polynomials we use to prove Theorem 1.1 : labeled binary forests. (This model was also introduced by Nadeau and Tewari in [ 9 ] ). Then, we will quickly review some combinatorics of permutations and pipe dreams. In section 3 , we describe a weight-preserving injection \psi_{w} sending labelings of a binary forest F to (reduced) pipe dreams for a permutation w (with the same code as F ). In section 4 , we show that if w contains a forbidden pattern, then our injection \psi_{w} cannot be surjective, proving one direction of Theorem 1.1 . Finally, in section 5 , we show that the forbidden patterns listed in Theorem 1.1 are the only possible obstructions to the bijectivity of \psi_{w} , completing the proof. 2 Preliminaries 2.1 Forest polynomials and indexed forests This subsection roughly summarizes the definitions given in section 3 of [ 9 ] . Let S be a finite set of positive integers; then, S decomposes as I_{1}\sqcup I_{2}\dots\sqcup I_{k} , where each I_{i} is a maximal subset of consecutive integers in S . A binary indexed forest F supported on S is the data of a binary tree T_{i} for each i\leq j , whose leaves are attached to the integers I_{i} . Figure 1 provides an example of such a binary indexed forest F . 1 2 3 4 5 6 7 8 9 10 F Figure 1: A binary indexed forest F . The non-leaf vertices of F are called interior vertices , denoted by \text{IN}(F) . These binary indexed forests will form our indexing set for the forest polynomials \mathfrak{F}_{F} . There is an important function \rho_{F}:\text{IN}(F)\to\mathbb{Z} . It sends an interior vertex v\in F to the leaf label reached by following left edges all the way down. Figure 2 illustrates the labeling yielded from applying \rho_{F} on each v\in F . 1 2 3 4 5 6 7 8 9 10 1 2 3 1 8 5 F Figure 2: Forest labeling f_{F} given by \rho_{F} for F from Figure 1 Definition 2.1 . A forest labeling f_{F}:\text{IN}(F)\to\mathbb{Z} is called valid if it satisfies the following three conditions: (i) For all v , f_{F}(v)\leq\rho_{F}(v) (ii) If w is a left child of v , then f_{F}(v)\leq f_{F}(w) and (iii) If w is a right child of v , then f_{F}(v)i|w(j)0}\times\mathbb{Z}_{>0} satisfying the following condition: the ordered product of the generators s_{i+j-1} over all (i,j)\in D (taken row by row from left to right, bottom to top) is a reduced word for w . From now on, all pipe dreams we consider will be reduced. The set of pipe dreams of w is denoted \text{PD}(w) . Every pipe dream D of w can be assigned a weight : \text{wt}(D)=\prod_{(i,j)\in D}x^{i} Bergeron and Billey [ 1 ] proved that pipe dreams for w correspond to monomials in \mathfrak{S}_{w} : Theorem 2.9 . \mathfrak{S}_{w}=\sum_{D\in\text{PD}(w)}\text{wt}(D) Pictorially, a pipe dream D can be viewed as a strand diagram : place a crossing at every (i,j)\in D and a pair of elbows at every (i,j)\notin D . The row of a crossing is j , and its column is i . This process results in a pseudo-line arrangement, where each strands connects (k,0) to (0,w(k)) and no two strands intersect more than once. Example 2.10 . Below are the two pipe dreams for w=4132 . The weight of the first pipe dream is x_{1}^{3}x_{3} and the weight of the second is x_{1}^{3}x_{2} , so, by Theorem 2.9 , \mathfrak{S}_{4132}=x_{1}^{3}x_{3}+x_{1}^{3}x_{2} . Every permutation has a distinguished pipe dream, called the bottom pipe dream , also defined and studied in [ 1 ] : Definition 2.11 . The bottom pipe dream of w is the unique left-justified pipe dream for w where the number of crossings in row i is L_{i} (where L(w) is the Lehmer code of w ). For example, the bottom pipe dream of 4132 is given by the left pipe dream in Example 2.10 . Bergeron-Billey [ 1 ] also gave a simple way to generate every pipe dream of w given its bottom pipe dream. Definition 2.12 . A ladder move of order k of D\in\text{RC}(w) applied at a crossing (i,j)\in D produces a new D^{\prime}\in\text{RC}(w) given by D\setminus\{(i,j)\}\cup\{(i-k-1,j+1)\} . A ladder move can only be applied at (i,j)\in D if two conditions are satisfied: (i) (i,j)\in D , and (i,j+1),(i-k-1,j),(i-k-1,j+1)\notin D and (ii) For all i-k\leq i^{\prime}f_{F}(w) . But since c_{w} was already assumed to be slid into row f_{F}(w) , we do not need to slide c_{v} any higher. To quickly summarize the argument, if a crossing c_{v} is obstructed by any other crossing c_{w} as it slides up to row f_{F}(v) , then the obstructing crossing c_{w} must satisfy f_{F}(w)\leq f_{F}(v) (with strict inequality if c_{w} is above c_{v} ). But this means that we have already slid c_{v} up to f_{F}(v) . ∎ Remark 3.11 . Suppose we have crossings c_{w},c_{v} corresponding to vertices w,v . Then if c_{w} lies in the diagonal d_{v}-1 or greater in P_{\text{bott}}(w) (equivalently c_{v} lies in the diagonal d_{w}+1 or smaller), v is in the subtree of w . Proof. If c_{w} has only empty rows following it, then the subtree of w is comprised of all rows which intersect diagonal d_{w}+1 . Nonempty rows can only increase the number of rows which are contained in the subtree of w , so any such v as described in the remark must be in the subtree of w . ∎ 4 Necessary direction In this section, we show that if a permutation w contains any of the permutations \{1432,2413,2431,14523,32154,341265\} , then its corresponding Schubert polynomial \mathfrak{S}_{w} is not a forest polynomial. 4.1 The forbidden patterns themselves Although it is easy to show by hand that \mathfrak{S}_{w} is not a forest polynomial for each forbidden w , it is useful to understand what is ‘bad’ about these patterns for our proof of the necessary direction. Below are the bottom pipe dreams of the six forbidden patterns: \bm{\mathsf{1}} \bm{\mathsf{2}} \bm{\mathsf{3}} \bm{\mathsf{4}} \bm{\mathsf{1}} \bm{\mathsf{2}} \bm{\mathsf{3}} \bm{\mathsf{4}} w=1432 \bm{\mathsf{1}} \bm{\mathsf{2}} \bm{\mathsf{3}} \bm{\mathsf{4}} \bm{\mathsf{1}} \bm{\mathsf{2}} \bm{\mathsf{3}} \bm{\mathsf{4}} w=2413 c_{w} : row 1, crossing 1 c_{v} : row 2, crossing 2 \bm{\mathsf{1}} \bm{\mathsf{2}} \bm{\mathsf{3}} \bm{\mathsf{4}} \bm{\mathsf{1}} \bm{\mathsf{2}} \bm{\mathsf{3}} \bm{\mathsf{4}} w=2431 c_{w} : row 1, crossing 1 c_{v} : row 2, crossing 2 \bm{\mathsf{1}} \bm{\mathsf{2}} \bm{\mathsf{3}} \bm{\mathsf{4}} \bm{\mathsf{5}} \bm{\mathsf{1}} \bm{\mathsf{2}} \bm{\mathsf{3}} \bm{\mathsf{4}} \bm{\mathsf{5}} w=14523 c_{w} : row 2, crossing 1 c_{v} : row 3, crossing 2 \bm{\mathsf{1}} \bm{\mathsf{2}} \bm{\mathsf{3}} \bm{\mathsf{4}} \bm{\mathsf{5}} \bm{\mathsf{1}} \bm{\mathsf{2}} \bm{\mathsf{3}} \bm{\mathsf{4}} \bm{\mathsf{5}} w=32154 c_{w} : row 1, crossing 2 c_{v} : row 4, crossing 1 \bm{\mathsf{1}} \bm{\mathsf{2}} \bm{\mathsf{3}} \bm{\mathsf{4}} \bm{\mathsf{5}} \bm{\mathsf{6}} \bm{\mathsf{1}} \bm{\mathsf{2}} \bm{\mathsf{3}} \bm{\mathsf{4}} \bm{\mathsf{5}} \bm{\mathsf{6}} w=341265 c_{w} : row 1, crossing 2 c_{v} : row 5, crossing 1 In each of these pipe dreams (except for 1432 ), we highlight a red crossing c_{w} and a blue crossing c_{v} . The pair (c_{w},c_{v}) always satisfies two properties: (i) The corresponding vertex v is the right child of w and (ii) It is possible to slide c_{v} , following some sequence of simple ladder moves, upwards so that c_{v} and c_{w} are in the same row. These two observations explain why each of these patterns is forbidden: in the forest F , we must have f_{F}(v)>f_{F}(w) , but there is a pipe dream for w such that \text{row}(v)\leq\text{row}(w) . That is, our injection \psi_{w} cannot be a surjection. Our general strategy in this direction will be to prove the existence of such a ‘bad’ parent-right child pair in P_{\text{bott}}(w) : Definition 4.1 . A pair of crossings (c_{w},c_{v})\in P_{\text{bott}}(w) is called a bad parent-child pair if: (i) c_{w} corresponds to the right child of c_{v} , but (ii) After some sequence of simple ladder moves (applied to c_{w} or other crossings), we can obtain a pipe dream in which c_{w} is in the same row as c_{v} . As explained above, if there exists a bad parent-child pair in P_{\text{bott}}(w) , then \mathfrak{S}_{w} cannot be a forest polynomial. In fact, using Proposition 3.5 , we have: Remark 4.2 . Suppose w avoids 1432 . Then, \mathfrak{S}_{w}\neq\mathfrak{F}_{F} if and only if there exists a ‘bad’ parent-right child pair as above. This remark will also be helpful for the sufficient direction. 4.2 Pattern avoidance and \psi_{w} First, we treat the pattern 1432 separately: Lemma 4.3 . If w contains \pi=1432 , \mathfrak{S}_{w} is not a forest polynomial. Proof. According to Proposition 3.5 , the image of the injection \psi contains only pipe dreams which can be obtained from P_{\text{bott}}(w) via simple ladder moves. However, w avoids 1432 if and only if every reduced pipe dream for w can be obtained from P_{\text{bott}}(w) via a sequence of simple ladder moves. Therefore, if w contains 1432 , the monomials appearing \mathfrak{S}_{w} are a strict superset of the monomials appearing in \mathfrak{F}_{T} . ∎ Now, let us consider only permutations which avoid 1432 . Our goal is to prove that if \mathfrak{S}_{\pi} is not a forest polynomial for a pattern \pi avoiding 1432 , then neither is \mathfrak{S}_{w^{\prime}} , for any w^{\prime} containing w as a pattern. Definition 4.4 . Given some permutation w\in S_{n} , let us define insertion at index i of value k as w^{\prime}=I_{i}^{k}(w) , where we obtain w^{\prime}\in S_{n+1} by adding at index i the value k\in[n+1] . Then, we increase by one all values w(j) with w(j)\geq k . For example, I_{2}^{4}(1342)=12453 . The following fact is standard: Lemma 4.5 . Given a permutation w containing a pattern \pi , we can obtain w from \pi by repeatedly performing insertions. Inserting values has a simple effect on \text{code}(w) . Namely, the bottom pipe dream of I_{i}^{k}(w) is obtained from P_{\text{bott}}(w) by inserting a new (possibly empty) row of crossings right before row i , and then, for all jw(i) . For example, L(1342)=(0,1,1,0) , and L(12453)=(0,0,1,1,0) . Lemma 4.6 . If a permutation \pi satisfies \mathfrak{S}_{\pi}\neq\mathfrak{F}_{T} , then any permutation w which contains \pi satisfies \mathfrak{S}_{w}\neq\mathfrak{F}_{T} . Proof. As remark 4.2 , we can find a ‘bad’ parent-right child pair c_{w},c_{v} in P_{\text{bott}}(\pi) (where c_{v} can slide up to the same row as c_{w} ). By Lemma 4.5 , we can repeatedly perform insertions to eventually obtain w from \pi . We will show that if we begin with such a pattern \pi and a pair of crossings (c_{w},c_{v}) , then any insertion I_{i}^{k}(w) will preserve the existence of such a pair, and thus we conclude that such a bad pair will exist in w . Let c_{w} slide along the d_{w} th northeast diagonal (northeast diagonals in the grid are labeled from top to bottom), and let c_{v} slide along the d_{v} th diagonal. Then, we must have d_{v}-d_{w}>1 (otherwise c_{w} and c_{v} would not be a bad pair; c_{w} would ‘block’ c_{v} from sliding past it). After each insertion, the parent of c_{v} is an element c_{k} on some diagonal d_{k}\leq d_{v} and row r_{k}\geq r_{v} . • If i\leq r_{w} (insert before row r_{w} ) then we retain the same pair (c_{w},c_{v}) . • If i>r_{v} (insert after row r_{v} ), since \pi(r_{v})<\pi(r_{w}) , if r_{w} obtains a new crossing in P_{\text{bott}}(w) , so must r_{v} . If r_{v} increases then let v^{\prime} be the crossing to the right of v ; our new bad pair will be (w,v^{\prime}) . • If r_{w}1 must be greater than 1 , otherwise c_{w} itself will always obstruct c_{v} from sliding into its row. Remark 5.3 . For a bad parent-child pair (c_{w},c_{v}) , c_{v} will always be the rightmost crossing in the row r_{v} , since all remaining crossings will be its left children. Lemma 5.4 . Let (c_{w},c_{v}) be a bad parent-child pair, with corresponding rows r_{w},r_{v} and diagonals d_{w},d_{v} . Then, if c_{v} can slide up to r_{w} via simple ladder moves without any other crossings performing any simple ladder moves, then w contains one of the following patterns: 2413 , 2431 , 32154 , 341265 . Proof. Note w(r_{v})-w(r_{w})>1 (in order for c_{v} to be able to slide up to r_{w} unobstructed, we must have L(r_{v})+(r_{w}-r_{v})-L(r_{w})\geq d_{v}-d_{w}>1\implies w(r_{v})-w(r_{w})\geq L(r_{v})+(r_{w}-r_{v})-L(r_{w})>1 where L(r_{v}) denotes entry r_{v} in the Lehmer code). There is some row x with w(r_{v})>w(x)>w(r_{w}) . Note if r_{v}>x>r_{w} then the rightmost crossing in row x must be on the diagonal below the rightmost crossing in row r_{w} , and by Remark 3.11 r_{w} would be in the subtree of x , which contradicts. Thus x>r_{v} . Since w(r_{w})\neq 1 , there is some y with w(y)r_{v} also, then whether xr_{v} . More specifically, there must be an x>r_{v} with w(x)x , we have a 2431 pattern. Finally, consider: Subcase 2: row r_{w} contains a crossing in d_{v}-1 , but not in d_{v} . In this case, we claim that w contains a 14523 pattern or a 1432 pattern. Because c_{v} can slide along its diagonal until it is directly beneath the rightmost crossing of row r_{w} , we have w(r_{w})r_{v} and w(r_{v})>w(x),w(y) . Finally, depending on the six possible relative orderings of w(r_{1}),w(x), and w(y) , indices r_{1},r_{w},r_{v},x,y give us one of the following patterns in w : (i) 15432 (ii) 25413 (iii) 25431 (iv) 35412 (v) 35421 or (vi) 15423 In the first three cases, there is a 1432 subpattern. In the next two cases, there is a 2431 subpattern. And in the last case, we have our last forbidden pattern, 15423 . ∎ Combining the two cases in Lemmas 5.4 and 5.5 gives us the sufficient direction of Theorem 1.1 . 6