Miriam Farber
email: mfarber@mit.edu

Yelena Mandelshtam

Arrangements Of Minors In The Positive Grassmannian And a Triangulation of The Hypersimplex

Keywords: the positive Grassmannian, sorted sets, triangulations, alcoved polytope, positroid stratification

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In this paper, we study the relations between equalities and inequalities of minors in the positive Grassmannian and the triangulation of the hypersimplex. This study is strongly tied to various combinatorial objects such as the positive Grassmannian and its stratification [START_REF] Postnikov | Total positivity, grassmannians, and networks[END_REF], alcoved polytopes [START_REF] Lam | Alcoved polytopes i[END_REF], sorted sets and Gröbner bases [START_REF] Sturmfels | Gröbner bases and convex polytopes[END_REF], as well as many other objects in algebraic combinatorics and beyond.

The notion of total positivity was originally introduced by Schoenberg [START_REF] Schoenberg | Über variationsvermindernde lineare transformationen[END_REF] and Gantmacher and Krein [START_REF] Gantmacher | Oscillation matrices and small oscillations of mechanical systems[END_REF] in the 1930s. The classical theory of total positivity deals with totally positive matricesmatrices in which all minors of all orders are positive. Later, the theory was extended by Lusztig in the general Lie theoretic setup through definition of the positive part for a reductive Lie group G and a generalized partial flag manifold G/P . In [START_REF] Postnikov | Total positivity, grassmannians, and networks[END_REF] it was shown that the space of totally positive matrices can be embedded in the positive Grassmannian, and this embedding unveils symmetries which are hidden on the level of matrices. Thus it is very natural to discuss equalities and inequalities of minors in the more general settings of the positive Grassmannian.

The number and positioning of equal minors in totally positive matrices was studied in several recent papers. In [START_REF] Farber | Equal entries in totally positive matrices[END_REF], it was shown that the number of equal entries in a totally positive n × n matrix is O(n 4/3 ). The authors also discussed positioning of equal entries and obtained relations to the Bruhat order of permutations. In [START_REF] Farber | On totally positive matrices and geometric incidences[END_REF] it was shown, using incidences between points and hyperplanes, that the maximal number of equal k × k minors in a k × n totally positive matrix is O(n k-k k+1 ). Inequalities between products of two minors in TP matrices have been widely studied as well [START_REF] Skandera | Inequalities in products of minors of totally nonnegative matrices[END_REF][START_REF] Rhoades | Temperley-lieb immanants[END_REF], and have close ties with Temperley-Lieb Immanants. Recently there has been also a study of products of three minors in such matrices [START_REF] Lam | Dimers, webs, and positroids[END_REF], that related such products with dimers. Despite all of the above, not much is known about the inequalities between the minors themselves. What is the full structure of all the possible equalities and inequalities between minors in TP matrices? The only part of this problem that has been solved discusses the structure of the minors with largest value and smallest value [START_REF] Farber | Arrangements of equal minors in the positive grassmannian[END_REF], while the rest of the problem remains open. The description in [START_REF] Farber | Arrangements of equal minors in the positive grassmannian[END_REF] involves rich combinatorial structure that relates arrangements of smallest minors with triangulations of the n-gon and the notion of weakly separated sets, while the structure of largest minors was related to thrackles and sorted collections. In this paper, we discuss the general case, and its tight relation with the triangulation of the hypersimplex.

Background

For n ≥ k ≥ 0, let the Grassmannian Gr(k, n) (over R) be the manifold of k-dimensional subspaces V ⊂ R n . It can be identified with the space of real k × n matrices of rank k modulo row operations. Here we assume that the subspace V associated with a k × n-matrix A is spanned by the row vectors of A. For such a matrix A and a k-element subset I ⊂ [n] := {1, 2, 3 . . . , n}, we denote by A I the k × k-submatrix of A in the column set I, and let ∆ I (A) := det(A I ). The coordinates ∆ I form projective coordinates on the Grassmannian, called the Plücker coordinates. In [START_REF] Postnikov | Total positivity, grassmannians, and networks[END_REF], the positive (nonnegative) Grassmannian Gr + (k, n) (Gr ≥ (k, n)) was defined to be the subset of Gr(k, n) whose elements are represented by k ×n matrices A with strictly positive (nonnegative) Plücker coordinates: ∆ I > 0 for all I.

We recall two classical stratifications of Gr(k, n) [START_REF] Postnikov | Total positivity, grassmannians, and networks[END_REF]. The first one is the cellular decomposition of Gr(k, n) into a disjoint union of Schubert cells. The Grassmannian Gr(k, n) also has a subdivision into matroid strata (or Gelfand-Serganova strata) S M labelled by matroids M . The nonnegative Grassmannian Arrangements Of Minors In The Positive Grassmannian And a Triangulation of The Hypersimplex 501 can be decomposed into cells via the positroid stratification. This decomposition has been studied by Postnikov in [START_REF] Postnikov | Total positivity, grassmannians, and networks[END_REF] and was described in terms of various combinatorial objects such as: decorated permutations, plabic graphs, L-diagrams, Grassmann necklaces, etc. The following stratification, which is finer than the positroid stratification, was suggested in [START_REF] Farber | Arrangements of equal minors in the positive grassmannian[END_REF], along with the problem bellow: Definition 2.1 Let U = (U 0 , U 1 , . . . , U l ) be an ordered set-partition of the set [n] k of all k-element subsets in [n]. Let us subdivide the nonnegative Grassmannian Gr ≥ (k, n) into the strata S U labelled by such ordered set partitions U and given by the conditions:

1. ∆ I = 0 for I ∈ U 0 , 2. ∆ I = ∆ J if I, J ∈ U i , 3. ∆ I < ∆ J if I ∈ U i and J ∈ U j with i < j.
An arrangement of minors is an ordered set-partition U such that the stratum S U is not empty.

Problem 2.2 Describe combinatorially all possible arrangements of minors in Gr ≥ (k, n). Investigate the geometric and the combinatorial structure of the stratification

Gr ≥ (k, n) = S U . Example 2.3 Let U 0 = ∅, U 1 = {3, 4} , U 2 = {1, 4} , U 3 = {1, 2}, {2, 3}, {1, 3}, {2, 4} . Then U = (U 0 , U 1 , U 2 , U 3
) is an ordered set partition of [4] 2 . Consider the matrix A = 1 2 1 1/3 1 3 2 1 .

The matrix A satisfies ∆ 34 = 1/3, ∆ 14 = 2/3, ∆ 12 = ∆ 23 = ∆ 13 = ∆ 24 = 1. Therefore S U is nonempty since A ∈ S U , and hence U is an arrangement of minors.

For the case k = 1, the stratification of Gr ≥ (k, n) into the strata S U is equivalent to Coxeter arrangement of type A (also known as braid arrangement). The classification of the possible options for U 0 is equivalent to the positroid stratification described above. In this work we deal with the positive Grammarian, and thus restrict ourself to the case U 0 = ∅. We extend the convention from [FP14]:

Definition 2.4 We say that a subset J ⊂ [n] k is an arrangement of t th largest (smallest) minors in Gr + (k, n), if there exists a nonempty stratum S U such that U 0 = ∅ and U l-t+1 = J (U t = J ).

If t = 1 we say that such arrangement is the arrangement of largest (smallest) minors.

Arrangements of largest and smallest minors were studied in [START_REF] Farber | Arrangements of equal minors in the positive grassmannian[END_REF], where it was shown that they enjoy a rich combinatorial structure. Arrangements of smallest minors are related to weakly separated sets. Such sets originally introduced by Leclerc-Zelevinsky [START_REF] Leclerc | Quasicommuting families of quantum plucker coordinates[END_REF] in the study of quasi-commuting quantum minors, and are closely related to the associated cluster algebra of the positive Grassmannian. Arrangement of largest minors were shown to be in bijection with simplices of Sturmfels' triangulation of the hypersimplex, which also appear in the context of Gröbner bases [START_REF] Lam | Alcoved polytopes i[END_REF]. In this paper, we are interested in the combinatorial description of arrangements of t th largest minors for t ≥ 2. For a stratum S U , the structure of U t for t < l depends on the structure of U l , as we will show later.

Definition 2.5 Let J ⊂ [n] k be an arrangement of largest minors. We say that Y ⊂ [n] k is a (t, J )-largest arrangement (t ≥ 2) if there exists a nonempty stratum S U such that U 0 = ∅, U l = J and U l-t+1 = Y.

We say that W ∈ [n] k can be (t, J )-largest minor if there exists a (t, J )-largest arrangement Y such that W ∈ Y

In particular, if Y ⊂ [n] k is a (t, J )-largest arrangement, then Y is also an arrangement of t th largest minors. For example, the first part of Example 2.3 implies that {3, 4} is a (3, {1, 2}, {2, 3}, {1, 3}, {2, 4} )-largest arrangement, and that {1, 4} can be (2, {1, 2}, {2, 3}, {1, 3}, {2, 4} )-largest minor.

3 The Triangulation of the Hypersimplex Definition 3.1 The hypersimplex ∆ k,n is an (n -1)-dimensional polytope defined as follows:

∆ k,n = {(x 1 , . . . , x n ) | 0 ≤ x 1 , . . . , x n ≤ 1; x 1 + x 2 + . . . + x n = k}.
It was shown in [START_REF] Stanley | Eulerian partitions of a unit hypercube[END_REF][START_REF] Sturmfels | Gröbner bases and convex polytopes[END_REF] that the normalized volume of ∆ k,n equals the Eulerian number A(n -1, k -1), that is, the number of permutations w of size n -1 with exactly k -1 descents. In [START_REF] Lam | Alcoved polytopes i[END_REF] four different constructions of a triangulation of the hypersimplex into A(n -1, k -1) unit simplices are presented: Stanley's triangulation [START_REF] Stanley | Eulerian partitions of a unit hypercube[END_REF], Alcove triangulation, circuit triangulation and Sturmfels' triangulation [START_REF] Sturmfels | Gröbner bases and convex polytopes[END_REF]. It was shown in [START_REF] Lam | Alcoved polytopes i[END_REF] that these four triangulations coincide. The rest of the section is devoted to Sturmfels' construction following the notations of [START_REF] Lam | Alcoved polytopes i[END_REF]. Definition 3.2 For a multiset S of elements from [n], let Sort(S) be the non-decreasing sequence obtained by ordering the elements of S. Let I, J ⊂ [n] k and let Sort(

I ∪ J) = (a 1 , a 2 , . . . , a 2k ). Define Sort 1 (I, J) := {a 1 , a 3 , . . . , a 2k-1 }, Sort 2 (I, J) := {a 2 , a 4 , . . . , a 2k }. A pair {I, J} is called sorted if Sort 1 (I, J) = I and Sort 2 (I, J) = J, or vise versa.
For example, {1, 3, 5}, {2, 4, 6} are sorted, while {1, 4, 5}, {2, 3, 6} are not sorted. The following Corollary follows from Skandera inequalities [START_REF] Skandera | Inequalities in products of minors of totally nonnegative matrices[END_REF].

Corollary 3.3 Let I, J ∈ [n]
k be a pair which is not sorted. Then ∆ sort1(I,J) ∆ sort2(I,J) > ∆ I ∆ J for points of the positive Grassmannian Gr + (k, n).

A collection I = {I 1 , I 2 , . . . , I r } of elements in [n] k is called sorted if I i , I j are sorted, for any pair 1 ≤ i < j ≤ n. Given I ∈ [n] k , let I be a 0,1-vector I = ( 1 , 2 , . . . , n ) such that i = 1 iff i ∈ I, and otherwise i = 0. For a sorted collection I, we denote by ∇ I the (r -1)-dimensional simplex with the vertices I1 , . . . , Ir .

Theorem 3.4 [START_REF] Sturmfels | Gröbner bases and convex polytopes[END_REF] The collection of simplices ∇ I where I varies over all sorted collections of kelement subsets in [n] , is a simplicial complex that forms a triangulation of the hypersimplex ∆ k,n .

From Theorem 3.4, it follows that the maximal by inclusion sorted collections correspond to the maximal simplices in the triangulation, and they are known to be of size n. As an example, consider the case k = 2. Let I = {a, b}, J = {c, d} ⊂ [n] 2 be a pair of sorted sets (I = J). Consider the graph G of order n whose vertices lie in clockwise order on a circle. Then we can think about I and J as edges in the graph, and since I and J are sorted, these two edges either share a common vertex or cross each other. Definition 3.5 A thrackle is a graph in which every pair of edges is either crossing or shares a common vertex. (i) The maximal number of edges in a thrackle is n, and each such maximal thrackle corresponds to a maximal sorted set with k = 2. Figure 1 describes all the thrackles of order up to 5.

(i) Our thrackles are a special case of Conway's thrackles. The latter are not required to have vertices arranged on a circle. . This graph has A(5, 1) = 26 vertices, each corresponds to a maximal thrackle on 6 vertices. We also described explicitly 6 of the vertices. In particular, vertices a and b are connected since b can be obtained from a by removing the edge {1, 6} and adding instead the edge {2, 5}. Therefore ∇ a and ∇ b share a common facet.

0 0 1 1 0 0 1 1 0 0
1 2 3 4 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 2 3 4 5 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1

Arrangements of minors and Sturmfels' triangulation

In this section, we describe necessary and sufficient conditions on arrangements of second largest minors, and also necessary conditions for arrangements of t-th largest minors for any t ≥ 2. The case t = 1, i.e., arrangements of largest minors, was fully resolved in [START_REF] Farber | Arrangements of equal minors in the positive grassmannian[END_REF]:

Theorem 4.1 A subset of J ⊂ [n]
k is an arrangement of largest minors in Gr + (k, n) if and only if it is a sorted subset. Equivalently, J is an arrangement of largest minors if and only if it corresponds to a simplex in Sturmfels' triangulation of the hypersimplex. Maximal arrangements of largest minors contain exactly n minors. The number of maximal arrangements of largest minors in Gr + (k, n) equals the Eulerian number A(n -1, k -1).

Theorem 4.1 implies that maximal arrangements of largest minors are in bijection with the vertices of Γ (k,n) . In this section, we will show that the structure of arrangements of second largest minors is strongly related the structure of edges in Γ (k,n) . As a warm-up, we start with the case k = 2.

4.1 The case k = 2: maximal thrackles Consider the space Gr + (2, n), and let J ⊂ [n] 2 be a maximal arrangement of largest minors (hence it corresponds to a maximal thrackle). Given W ∈ [n] 2 , we ask whether W can be (2, J )-largest minor. That is, whether there exists an element in Gr + (2, n) in which the collection of largest minors is J and W is second largest. Our theorem bellow gives necessary and sufficient conditions on such W . Theorem 4.2 Let W ∈ [n] 2 and let J ⊂ [n] 2 be some maximal arrangement of largest minors. The following four statements are equivalent.

1. W can be (2, J )-largest minor.

2. There exist a vertex Q in Γ (2,n) that is adjacent to J , such that W ∈ Q.

3. There exist J ∈ J such that (J \ J) ∪ W is an arrangement of largest minors. In particular, the minors that can be second largest are in bijection with the edges of Γ (2,n) that are connected to vertex J , and the number of such minors is at most n.

We emphasize the relation, implied by our theorem, between arrangements of second largest minors and the structure of Γ (2,n) . Let J ⊂ [n] 2 be a maximal thrackle, and let

T = {A ∈ Gr + (2, n) | the set of largest minors of A is J }. Let W ∈ [n]
2 . Theorem 4.2(2) implies that there exists A ∈ T for which W is the second largest minor if and only if there exists a vertex Q in Γ (2,n) that is adjacent to J such that W ∈ Q.

Example 4.3 Consider the maximal thrackle J in Figure 3 on the left. Using part (4) of Theorem 4.2, we identify the elements in [n] 2 that can be second largest minors, and denote them by red lines (and this is the second graph from the left). Then, in Figure 3 on the right, we describe the thrackle resulted in adding the red line and removing one of the edges of J . Those three cases correspond to the three edges that are connected to J in Γ (2,5) .

The general case

In the previous section, we considered the space Gr + (2, n) and discussed arrangements of second largest minors. In this section we consider the space Gr + (k, n), and discuss arrangements of t th largest minors (t ≥ 2). Our discussion covers the general case (that is, we will make no assumption on the arrangements of largest minors). We start with the case t = 2.

Theorem 4.4 Let W ∈ [n] k and let J ⊂ [n] k be some arrangement of largest minors. Denote |J | = c. If W can be (2, J )-largest minor, then one of 1,2 holds, or equivalently, one of 3,4 holds:

1. The collection {W } ∪ J is sorted 2. There exists J ∈ J such that W and J are not sorted, and (J \ J) ∪ {W } is a sorted collection.

3. ∇ {W }∪J is a c-dimensional simplex in Sturmfels triangulation of the hypersimplex ∆ k,n .

4. There exists a c -1-dimensional simplex ∇ Y in Sturmfels triangulation such that W is a vertex in ∇ Y , and the simplices ∇ Y ,∇ J share a common facet.

The proof idea is to show that if there exist two elements J 1 , J 2 ∈ J that are not sorted with W , then the collection {J 1 , J 2 , Sort 1 (W, J 1 ), Sort 2 (W, J 1 ), Sort 1 (W, J 2 ), Sort 2 (W, J 2 )} cannot be sorted. Therefore, not all the elements in the collection can be in the arrangement of largest minors. From here we can use Skandera inequalities and deduce that W cannot be second largest. The theorem above gives a necessary condition on second largest minors. If J from Theorem 4.4 is maximal, we obtain sufficient conditions as well. The following generalize Theorem 4.2.

Theorem 4.5 Let W ∈ [n] k and let J ⊂ [n] k be some maximal arrangement of largest minors. The following two statements are equivalent.

1. W can be (2, J )-largest minor.

2. There exist a vertex Q in Γ (k,n) that is adjacent to J , such that W ∈ Q.

In particular, the minors that can be second largest are in bijection with the edges of Γ (k,n) that connected to vertex J , and the number of such minors is at most n.

In one direction the proof follows from Theorem 4.4. The second direction is proven using properties of the torus action on the positive Grassmannian. Theorem 4.5 states that when J is a maximal sorted set, the second largest minor must appear in one of the neighbors of J in Γ (k,n) . In order to discuss t th largest minors for t > 2, we will introduce the notion of cubical distance in the graph Γ (k,n) . Consider the blue edges in Figure 2, and note that they form a square, while the red edges form a 3-dimensional cube. We say that two vertices J 1 , J 2 in Γ (k,n) are of cubical distance 1 if both of them lie in certain cube (of any dimension). For example, vertices a and b from Figure 2 are of cubical distance 1 since both of them lie in a 1-dimensional cube (which is just an edge). similarly, a and c are of cubical distance 1 (both of them lie in a square), as well as c and d (both of them lie in a 3-dimensional cube).

Definition 4.6 Let J 1 , J 2 ⊂ [n]
k be maximal sorted collections, and let W ∈ [n] k . We say that J 1 , J 2 are of cubical distance D, and denote it by cube d (J 1 , J 2 ) = D, if one can arrive from J 1 to J 2 by moving along D cubes in Γ (k,n) , and D is minimal with respect to this property. We say that W is of cubical distance D from J 1 , and denote it by cube d (J 1 , W ) = D, if for any vertex J 2 in Γ (k,n) that contains W , cube d (J 1 , J 2 ) ≥ D, and for at least one such J 2 this inequality becomes equality.

For example, using the notations of Figure 2, cube d (a, d) = 2, cube d (b, d) = 2, cube d (a, e) = 3. We also have cube d (a, {1, 4}) = 1 since {1, 4} ∈ f , and cube d (a, {2, 4}) = 2 since {2, 4} / ∈ b, f, c, {2, 4} ∈ d. It can also be shown that cube d (a, {2, 3}) = 3. Definition 4.7 Let J ⊂ [n] k be an arrangement of largest minors, and let W ∈ [n] k . We say that W is (≥ t, J )-largest minor if for any arrangement of minors U = (U 0 , U 1 , . . . , U l ) such that U l = J the following holds: W / ∈ U l , U l-1 , . . . , U l-t+2 .

For example, let J be the maximal sorted collection that corresponds to vertex a in Figure 2, and let A ∈ Gr + (2, 6) in which the collection of maximal minors is J . Using Skandera's inequalities, it is possible to show that for such A,

∆ 16 > ∆ 14 > ∆ 24 > ∆ 23 . Therefore, {2, 3} is (≥ 4, U l )-largest minor, since {2, 3} / ∈ U l , U l-1 , U l-2 Conjecture 4.8 Let W ∈ [n]
k and let J ⊂ [n] k be some maximal arrangement of largest minors. If

cube d (W, J ) = t, then W is (≥ t + 1, U l )-largest minor.
Note that the examples we gave earlier are special cases of this conjecture. For example, cube d (a, {2, 3}) = 3, and indeed {2, 3} is (≥ 4, U l )-largest minor. Theorem 4.9 Conjecture 4.8 holds for t = 2, 3 (and any n ,k), and also for k = 2 (and any n, t).

At first glance, it may seem like Theorem 4.9 contradicts Theorem 4.5 since a vertex J 2 of cubical distance 1 from J doesn't have to be connected to J . However, it can be shown that if W ∈ J 2 then W also appears in one of the neighbors of J . In the next section, we will prove additional cases of the conjecture. Conjecture 4.8 deals with the case in which J is maximal. We will now discuss general case, in which J can be any sorted collection. Theorem 4.4 implies that if W ∈ [n] k is a second largest minor, then W is "close" to ∇ J . This notion of distance is formally defined in the following definition. This definition allows us to generalize this property for arrangements of t th largest minors (t ≥ 2) Definition 4.10 Let r be an integer, 1 ≤ i ≤ j ≤ n, and denote by H i,j,r the affine hyperplane

{x i + x i+1 • • • + x j = r} ⊂ R n . Fix a point x ∈ R n .
For y ∈ R n , we say that H i,j,r separates y from x if one of the following holds:

• x and y lie in the two disjoint halfspaces formed by H i,j,r .

• y lies on H i,j,r and x does not.

Define d ij (x, y) = |{r| the hyperplane H i,j,r separates y from x}|. Finally, let B r (x) = {y | d ij (x, y) ≤ r for all 1 ≤ i ≤ j ≤ n}.
The notion d ij arises naturally in the discussion of sorted sets. In particular, by [LP07, section 2.4], I and J are sorted if and only if

d ij ( I , J ) ≤ 1 for every 1 ≤ i ≤ j ≤ n.
Theorem 4.11 Let J ⊂ [n] k be some arrangement of largest minors, and let Y be a (t, J )-largest arrangement. Then the following holds:

• If t = 2, then Y ∈ B 2 (J) for any Y ∈ Y, J ∈ J . • If t ≥ 3, then Y ∈ B 2+2 t-3 (J) for any Y ∈ Y, J ∈ J .
Thus, we get that if W can be (t, J )-largest minor, then W must lie within a ball of certain bounded radius around J . We conclude this section with the following corollary.

Corollary 4.12 Let Y be an arrangement of t th largest minor, t ≥ 2. Then all the elements Y , Y ∈ Y lie within a ball of radius 2 + 2 t-3 .

Circuit triangulation and partially ordered set of minors

In this section, we show that arrangements of largest minors induces a structure of partially ordered set on the entire collection of minors. We investigate this poset, and its relations to arrangements of minors.

Example 5.1 Let k = 2, n = 6, and let A ∈ Gr + (2, 6) be an element for which the minors that appear in Figure 4 on the left are maximal. Thus, without loss of generality, we can assume that By Theorem 4.1, all the other minors are strictly smaller than 1. However, there is much more information that we can obtain on the order of the minors. For example, using 3-term Plücker relation, we get ∆ 46 ∆ 13 < ∆ 14 ∆ 36 , and hence ∆ 46 < ∆ 36 . Once the set of largest minors is fixed, it induces a structure of partially ordered set on the collection of minors. Figure 4 depicts the Hasse diagram that corresponds to the example above (and the relation ∆ 46 < ∆ 36 is one of the covering relations in this diagram).

∆ 12 = ∆ 13 = ∆ 14 = ∆ 15 = ∆ 25 = ∆ 26 = 1.
In order to discuss these partially ordered set more systematically, we will use the circuit triangulation of the hypersimplex. It was introduces in [START_REF] Lam | Alcoved polytopes i[END_REF], and was shown to be isomorphic to Sturmfels triangulation.

Definition 5.2 We define G k,n to be the directed graph whose vertices are { I } I∈( [n] k ) , and two vertices = ( 1 , 2 , . . . , n ) and are connected by an edge oriented from to if there exists some i ∈ [n] such that ( i , i+1 ) = (1, 0) and the vector is obtained from by switching i , i+1 (and leaving all the other coordinates unchanged, so the 1 is "shifted" one place to the right). We label such edge by i. When considering i ∈ [n] we refer to i as i mod n, and thus if i = n, we have i + 1 = 1.

A circuit in G k,n of minimal possible length must be of length n. The left part of Figure 5 is an example of a minimal circuit in G 3,8 . For convenience, we label the vertices by I instead of I . The sequence of labels of edges in a minimal circuit forms a permutation ω = ω 1 ω 2 . . . ω n ∈ S n , and two permutations that obtained from each other by cyclic shifts correspond to the same circuit. Thus, we can label each minimal circuit in G k,n by its permutation modulo cyclic shifts. For example, the permutation corresponding to the minimal circuit in Figure 5 is ω = 56178243, and we label this circuit by C ω .

Theorem 5.3 [START_REF] Lam | Alcoved polytopes i[END_REF] Each minimal circuit C ω in G k,n determines the simplex ∆ w inside the hypersimplex ∆ k,n with the vertex set C ω . The collection of simplices ∆ ω corresponding to all minimal circuits in G k,n forms a triangulation of the hypersimplex, which is called the circuit triangulation. The vertices of C ω form a maximal sorted collection, and every maximal sorted collection can be realized via a minimal circuit in the graph G k,n .

The structure of G k,n is quite complicated in general. Yet, we found an algorithm that recognizes certain planar subgraphs of G k,n -these subgraphs induce a structure of partial order on the set of minors.

Definition 5.4 An oriented Young graph is the graph that is obtained from a Young diagram after orienting each horizontal edge from right to left and each vertical edge from top to bottom. We call the vertex that is in the upper left corner the origin vertex, and denote the upper right (lower left) vertex by v 0 (v 1 ). There are two paths that start at v 0 , walk along the border end at v 1 . The path that passes through the origin vertex is called inner path, and the second path is called outer path. From now on, we denote the set of the vertices appear in the outer path by V . See the right part of Figure 5 for example. Lemma 5.5 Let H be an oriented Young subgraph of G k,n , and let A ∈ Gr + (k, n) for which all the minors indexed by V are equal and have largest value. Then for any vertex I of H such that I / ∈ V , we have ∆ I < ∆ J , ∆ I < ∆ Z where J is the vertex right bellow I and Z is the vertex to the right of I in H (see Figure 5). Definition 5.6 Let H be an oriented Young subgraph of G k,n , and let u be the origin vertex. The swapping distance between u and V is max{i + j -1|(i, j) ∈ H}.

For example, the swapping distance of u from V in Figure 5 is 5.

Corollary 5.7 Let H, V, u be as in Lemma 5.5, and denote by t the swapping distance of u from V . Let U l ⊂ [n] k such that V ⊂ U l . Then u is (≥ t + 1, U l )-largest minor.

Lemma 5.8 Let J ⊂ [n] k be a maximal sorted collection, and suppose that there exists an oriented Young subgraph H of G k,n such that V ⊂ J . Let u be the origin vertex in H. Then cube d (J , u) is bounded from above by the swapping distance of u from V . Theorem 5.9 If W is sorted with at least one element in J , then the claim in Conjecture 4.8 holds. The proof idea of Theorem 5.9 is that under the conditions of the theorem, one can find an oriented Young subgraph of G k,n such that W is the origin vertex and V ⊂ J . Then we apply Lemma 5.5. The existence of such subgraph not only implies Theorem 5.9, but also induces a poset on the collection of minors, as each minor in the Young subgraph (that is not in J ) is smaller than the minor to the right of it and the minor bellow it. Let us show an example. Suppose that the minors corresponding to the circuit C ω in Figure 5 form a collection J of largest minors, and let W = (3, 5, 6). Among the vertices of C ω , W is sorted with {1, 3, 5}, {1, 4, 5}, {1, 4, 6}, and not sorted with the rest. So the set of vertices that are not sorted with W form a path in C ω , and this property also holds in the general case. We would like to construct an alternative path in G 3,8 that starts at {1, 4, 6}, ends at {1, 3, 5} and contains only vertices that are sorted with W . Consider the left graph G 1 that appears in Figure 6. G 1 is a subgraph of the graph G 3,8 , and the edges that correspond to the circuit C ω appear as dotted lines. The part of ω that corresponds to the dotted lines is 617824 (we ignore the vertex {1, 4, 5}, as it is sorted with W ). Let us instead start at {1, 4, 6} and walk along the path 124678. Note that after 3 steps in this path, we arrive to the vertex W . The bottom right graph in Figure 6 is the oriented Young subgraph (in the figure it appears rotated) of G 3,8 in which the set V is consisted of vertices from C ω and W is the origin vertex. One can check that this is indeed a subgraph of G 1 . Similar claim holds in the case W = (2, 5, 6), with the corresponding

Fig. 1 :

 1 Fig. 1: All maximal thrackles that have at most 5 vertices (up to rotations and reflections).

Figure 2

 2 Figure2depicts the graph Γ (2,6) . This graph has A(5, 1) = 26 vertices, each corresponds to a maximal thrackle on 6 vertices. We also described explicitly 6 of the vertices. In particular, vertices a and b are connected since b can be obtained from a by removing the edge {1, 6} and adding instead the edge {2, 5}. Therefore ∇ a and ∇ b share a common facet.

Fig. 2 :

 2 Fig. 2: The graph Γ (2,6)

  4. There exist four distinct vertices labelled a, a + 1, b, b + 1 mod n such that {(a, b), (a -1, b), (b + 1, a)} ⊂ J and W = (a -1, b + 1).

  Fig.3

Fig. 4 :

 4 Fig. 4: A maximal thrackle and the corresponding poset of minors

Fig. 5 :

 5 Fig. 5: The figure on the left is a circuit in G 3,8 . The right figure is an oriented Young graph. It's inner boundary path formed by the edges labeled from 1' through 8'. Its outer boundary path formed by the edges labeled from 1 through 8, and all the vertices that appear along the latter path form the collection V.

  Fig.6

Acknowledgements

We would like to thank Alexander Postnikov for useful discussions.


Arthur L B Yang
email: yang@nankai.edu.cn

Philip B Zhang

The Real-rootedness of Eulerian Polynomials via the Hermite-Biehler Theorem

Keywords: Eulerian polynomials, Hermite-Biehler Theorem, Borcea and Brändén's stability criterion, weak Hurwitz stability

Based on the Hermite-Biehler theorem, we simultaneously prove the real-rootedness of Eulerian polynomials of type D and the real-rootedness of affine Eulerian polynomials of type B, which were first obtained by Savage and Visontai by using the theory of s-Eulerian polynomials. We also confirm Hyatt's conjectures on the interlacing property of half Eulerian polynomials. Borcea and Brändén's work on the characterization of linear operators preserving Hurwitz stability is critical to this approach.

Résumé. Basé sur le théorème de Hermite-Biehler, nous prouvons simultanément les polynômes eulériens de type D et les polynômes eulériens affine de type B ont seulment racines réelle, qui sont d'abord obtenue par Savage et Visontai en utilisant le théorie des polynômes s-eulériens. Nous confirmons aussi les conjectures de Hyatt sur la propriété entrelacement de polynômes mi-eulériens. Le travail de Borcea et Brändén sur la caractérisation des opérateurs linéaires préservant la stabilité Hurwitz est essentielle à cette approche.

Introduction

Brenti [START_REF] Brenti | q-Eulerian polynomials arising from Coxeter groups[END_REF] introduced the notion of Eulerian polynomials for finite Coxeter groups. Let W be a finite Coxeter group with generators s 1 , s 2 , . . . , s n . The length of each σ ∈ W is defined as the number of generators in one of its reduced expressions, denoted (σ). We say that i is a descent of σ if (σs i ) < (σ). Let des σ denote the number of descents. The Eulerian polynomial of W is defined by

W (x) = σ∈W x des σ .
If W is of type A n (resp. B n or D n ), then we simply write A n (x) (resp. B n (x) or D n (x)) for W (x). It is well known that A n (x) is the classical Eulerian polynomial. Brenti [START_REF] Brenti | q-Eulerian polynomials arising from Coxeter groups[END_REF] conjectured that, for any finite irreducible Coxeter group W , the polynomial W (x) has only real zeros, and left the case of D n (x) open.

Dilks, Petersen, and Stembridge [START_REF] Dilks | Affine descents and the Steinberg torus[END_REF] studied the affine descent statistic, which is defined by Cellini [START_REF] Cellini | A general commutative descent algebra[END_REF], and proposed a companion conjecture. Suppose that W is an irreducible finite Weyl group with generators s 1 , s 2 , . . . , s n . Let s 0 be the reflection corresponding to the highest root. For each σ ∈ W , we say that i is an affine descent of σ if either i = 0 and (σs 0 ) > (σ) or i is a descent for 1 ≤ i ≤ n. Denote des σ the number of affine descents of σ. Analogous to the definition of W (x), the affine Eulerian polynomial of W is defined as

W (x) = σ∈W x des σ .

Similarly, we use

A n (x) (resp. B n (x) or D n (x)) to represent W (x) when W is of type A n (resp. B n or D n ).
Dilks, Petersen, and Stembridge [START_REF] Dilks | Affine descents and the Steinberg torus[END_REF] conjectured that, for any irreducible Weyl group, the affine Eulerian polynomial has only real zeros and left the cases of B n (x) and D n (x) open.

By using the theory of s-Eulerian polynomials, Savage and Visontai [START_REF] Savage | The s-Eulerian polynomials have only real roots[END_REF] proved the real-rootedness of D n (x) and B n (x), and hence completely confirmed Brenti's conjecture on Eulerian polynomials for finite Coxeter groups. In particular, Savage and Visontai [START_REF] Savage | The s-Eulerian polynomials have only real roots[END_REF] obtained the following result.

Theorem 1.1 Both D n (x) and B n (x) have only real zeros. Moreover, we have

D n (x) B n (x).
Furthermore, Yang and Zhang [START_REF] Yang | Mutual interlacing and Eulerian-like polynomials for Weyl groups[END_REF] proved the real-rootedness of D n (x), and hence completely confirmed Dilks, Petersen, and Stembridge's conjecture on affine Eulerian polynomials.

The key idea to prove Brenti's conjecture and Dilks, Petersen, and Stembridge's conjecture is to find some proper refinement of s-Eulerian polynomials, and then to prove that the refined s-Eulerian polynomials satisfy certain interlacing property. Given two real-rooted polynomials f (z) and g(z) with positive leading coefficients, let {r i } be the set of zeros of f (z) and {s j } the set of zeros of g(z). We say that g(z)

interlaces f (z), denoted g(z) f (z), if • • • ≤ s 2 ≤ r 2 ≤ s 1 ≤ r 1 .
Recently, Hyatt [START_REF] Hyatt | Recurrences for Eulerian polynomials of type B and type D[END_REF] proposed another approach to Brenti's conjecture on the real-rootedness of Eulerian polynomials by considering the interlacing property of half Eulerian polynomials. Recall that the Coxeter group B n of type B of rank n can be regarded as the group of all bijections π of the set ±[n] = {±1, ±2, . . . , ±n} such that π(-i) = -π(i) for all i ∈ ±[n]. We usually write π in one-line notation (π 1 , π 2 , . . . , π n ), where π i = π(i). The half Eulerian polynomials of type B are given by

B + n (x) = σ∈Bn:σn>0
x des B σ and B - n (x) = σ∈Bn:σn>0

x des B σ .

The Coxeter group D n of type D of rank n is composed of those even signed permutations of B n . In the same manner, the half Eulerian polynomials of type D are defined as

D + n (x) = σ∈Dn:σn>0
x des D σ and D - n (x) = σ∈Dn:σn>0

x des D σ .

Hyatt proposed the following conjectures, which have been confirmed by himself in the new version of [START_REF] Hyatt | Recurrences for Eulerian polynomials of type B and type D[END_REF].

) (i) For n ≥ 1 , B + n (x) interlaces x n B + n (1/x) and thus B n (x) = B + n (x) + x n B + n (1/x) has only real zeros. (ii) For n ≥ 2 , D + n (x) interlaces x n D + n (1/x) and thus D n (x) = D + n (x) + x n D + n (1/x) has only real zeros.
In this paper, we shall show that both Theorem 1.1 and Conjecture 1.2 can be derived from the Hurwitz stability of certain polynomials.

Stability

In this section, we shall give an overview of some fundamental results on Hurwitz stability, which serve as basic tools for our proofs of Theorem 1.1 and Conjecture 1.2.

Let C[z] denote the set of all polynomials in z with complex coefficients. Recall that a polynomial P (z) ∈ C[z] is said to be weakly Hurwitz stable (resp. Hurwitz stable) if P (z) = 0 whenever Re z > 0 (resp. Re z ≥ 0), where Re z denotes the real part of z. This concept has been extended to multivariate polynomials. Let C[z 1 , z 2 , . . . , z n ] denote the set of polynomials in z 1 , z 2 , . . . , z n . We say that P (z 1 , z 2 , . . . , z n ) ∈ C[z 1 , z 2 , . . . , z n ] is weakly Hurwitz stable (resp. Hurwitz stable) if

P (z 1 , z 2 , . . . , z n ) = 0 for all tuples (z 1 , z 2 , . . . , z n ) ∈ C n with Re z i > 0 (resp. Re z i ≥ 0) for 1 ≤ i ≤ n.
The first tool to be used is the Hermite-Biehler theorem, a basic result in the Routh-Hurwitz theory [START_REF] Rahman | Analytic Theory of Polynomials[END_REF]. Suppose that

P (z) = n k=0 a k z k . Let P E (z) = n/2 k=0 a 2k z k and P O (z) = (n-1)/2 k=0 a 2k+1 z k . ( 1
)
As shown below, the stability of P (z) is closely related to the interlacing property between P E (z) and P O (z).

Theorem 2.1 ([6, Theorem 4.1], [12, pp. 197]) Let P (z) be a polynomial with real coefficients, and let P E (z) and P O (z) be defined as in [START_REF] Adinh | Descent numbers and major indices for the hyperoctahedral group[END_REF]. Suppose that P E (z)P O (z) ≡ 0. Then P (z) is weakly Hurwitz stable if and only if P E (z) and P O (z) have only real and non-positive zeros, and P O (z) P E (z).

The second tool to be used is Borcea and Brändén's characterization of linear operators preserving weakly Hurwitz stability, see [START_REF] Borcea | The Lee-Yang and Pólya-Schur programs. I. Linear operators preserving stability[END_REF]. Let C m [z] denote the set of polynomials over C with degree less than or equal to m.

T [(zw + 1) m ] := m k=0 m k T (z k )w k (2)
is weakly Hurwitz stable in two variables z, w.

The polynomial T [(zw + 1) m ] is called the algebraic symbol of the linear operator T .

With the above theorem, we obtain the following result, which plays an important role in our approach to Theorem 1.1 and Conjecture 1.2.

Theorem 2.3 For any positive integer n ≥ 2 and any real number k ≥ -n, the polynomial

P n (x) = (x + 1)A n-1 (x) + kxA n-2 (x)
is weakly Hurwitz stable.

Proof: It is known that the Eulerian polynomials A n (x) satisfy the following recurrence relation:

A n (x) = (nx + 1) A n-1 (x) -x(x -1)A n-1 (x) = (n + 1)(xA n-1 (x)) -(x -1)(xA n-1 (x)) ,
with the initial condition A 0 (x) = 1. Thus, we find that

P n (x) = (nx + n + k) (xA n-2 (x)) -x 2 -1 (xA n-2 (x)) .
This formula could be restated as

P n (x) = T (xA n-2 (x)),
where

T = (nx + n + k) -(x 2 -
As a final tool we shall need the Routh-Hurwitz stability criterion, which was given by Hurwitz [START_REF] Hurwitz | Ueber die Bedingungen, unter welchen eine Gleichung nur Wurzeln mit negativen reellen Theilen besitzt[END_REF]. For more historical background on this criterion, see [12, pp. 393]. Given a polynomial

P (z) = n k=0 a n-k z k , for any 1 ≤ k ≤ n, let ∆ k (P ) = det         a 1 a 3 a 5 . . . a 2k-1 a 0 a 2 a 4 . . . a 2k-2 0 a 1 a 3 . . . a 2k-3 0 a 0 a 2 . . . a 2k-r . . . . . . . . . . . . . . . 0 0 0 . . . a k         k×k .
These determinants are known as the Hurwitz determinants of P (z). Hurwitz showed that the stability of P (z) is uniquely determined by the signs of ∆ k (P ).

Theorem 2.4 ( [START_REF] Hurwitz | Ueber die Bedingungen, unter welchen eine Gleichung nur Wurzeln mit negativen reellen Theilen besitzt[END_REF]) Suppose that P (z) = n k=0 a n-k z k is a real polynomial with a 0 > 0. Then P (z) is Hurwitz stable if and only if the corresponding Hurwitz determinants ∆ k (P ) > 0 for any 1 ≤ k ≤ n.

Interlacing

The main objective of this section is to prove Theorem 1.1 and Conjecture 1.2.

Let us first review some formulas on the Eulerian polynomials. For Eulerian polynomials of type A and B, it is known that

A n-1 (x) (1 -x) n+1 = i≥0 (i + 1) n x i , (3)
and

B n (x) (1 -x) n+1 = i≥0 (2i + 1) n x i , (4)
see [START_REF] Brenti | q-Eulerian polynomials arising from Coxeter groups[END_REF] and references therein.

Conjecture 1 . 2 (

 12 [START_REF] Hyatt | Recurrences for Eulerian polynomials of type B and type D[END_REF] Corollaries 4.6 and 4.8]

Theorem 2 . 2 ([ 5 ,

 225 Theorem 8], [4, Theorem 3.2]) Let m ∈ N and T : C m [z] → C[z] be a linear operator. Then T preserves weak Hurwitz stability if and only if (a) T has range of dimension at most one and is of the form T (f ) = α(f )P , where α is a linear functional on C m [z] and P is a weakly Hurwitz stable polynomial, or (b) The polynomial

  Note that Re x > 0 if and only if |z| > 1. It is obvious that If Re x > 0 and Re y > 0, then |z| > 1 and |w| > 1, and hence |zw| > 1. Therefore, we have Re zw-1 zw+1 > 0 and thus Re x+y xy+1 > 0. Moreover, it is clear that xy + 1 = 0 whenever Re x > 0 and Re y > 0. It follows that T [(xy + 1) n ] is weakly Hurwitz stable in variables x, y.By Theorem 2.2 , the linear operator T preserves stability. The weak Hurwitz stability of P n (x) immediately follows from that of xA n-2 (x). This completes the proof.

		x + y xy + 1	=	zw -1 zw + 1	.
							1)	d dx
	denotes the operator acting on C n [x]. It is easy to see that T is a linear operator. The algebraic symbol of
	T is given by
	T [(xy + 1) n ] = (xy + 1) n-1 ((k + n)(xy + 1) + n(x + y))
	= n(xy + 1) n x + y xy + 1	+	k + n n	.
	We claim that	x + y xy + 1	+	k + n n
	is weakly Hurwitz stable in variables x, y if k ≥ -n. To prove this, let
	x =	z -1 z + 1	,				y =	w -1 w + 1	.

By [START_REF] Athanasiadis | A symmetric unimodal decomposition of the derangement polynomial of type B[END_REF] and (4), we have

which leads to the following identity,

For Eulerian polynomials of type D, Stembridge [START_REF] Stembridge | Some permutation representations of Weyl groups associated with the cohomology of toric varieties[END_REF]Lemma 9.1] discovered that D n (x) has a close connection with the Eulerian polynomials of type A and B:

For affine Eulerian polynomials of type B, Dilks, Petersen, and Stembridge [9, Proposition 6.3] established the following identity:

The first main result of this section is as follows.

Theorem 3.1 We have

Proof: By ( 6) and [START_REF] Brenti | q-Eulerian polynomials arising from Coxeter groups[END_REF], we obtain that

where the desired identity follows from [START_REF] Borcea | Pólya-Schur master theorems for circular domains and their boundaries[END_REF]. This completes the proof. 2

Now we can give a proof of Theorem 1.1.

Proof of Theorem 1.1: By Theorem 2.3, the polynomial

is weakly Hurwitz stable. Combining (8) and Theorem 2.1, we complete the proof of Theorem 1.1. 2

We proceed to prove Hyatt's conjectures on half Eulerian polynomials. Here we need the combinatorial characterization of the descent statistic and the affine descent statistic, see Brenti [START_REF] Brenti | q-Eulerian polynomials arising from Coxeter groups[END_REF] and Dilks, Petersen, and Stembridge [START_REF] Dilks | Affine descents and the Steinberg torus[END_REF].

From the equality that [3, (7.5) ]

as well as ( 4) and the fact that

Similar with [START_REF] Borcea | Pólya-Schur master theorems for circular domains and their boundaries[END_REF], it follows from (3), [START_REF] Dilks | Affine descents and the Steinberg torus[END_REF], and ( 10) that From the involution on B n that changes the sign of the first element in the one-line notation, it follows that

By further considering the combinatorial characterization of the descent statistic of type D and the affine descent statistic of type B, we obtain that

Together with the fact that D n (x) = D + n (x) + D - n (x), (8) turns out to be

It is not too hard to prove by the bijection from B + n to B + n that changes all signs of the elements in one-line notation (see [START_REF] Athanasiadis | A symmetric unimodal decomposition of the derangement polynomial of type B[END_REF]Lemma 7.1]), it follows that

The second main result of this section is as follows, which gives an affirmative answer to Conjecture 1.2.

Proof of Conjecture 1.2: Let us first prove (i). Since (x + 1) n A n-1 (x) has only non-positive real zeros, Theorem 2.1 together with [START_REF] Hyatt | Recurrences for Eulerian polynomials of type B and type D[END_REF] implies that B + n (x) interlaces B - n (x). By [START_REF] Sloane | On-line encyclopedia of integer sequences[END_REF], this shows that B + n (x) interlaces x n B + n (1/x). The proof is complete.

In the same manner, we can prove (ii). Note that, by Theorem 2.3, the polynomial

is weakly Hurwitz stable. Thus D + n (x) interlaces D - n (x) by [START_REF] Savage | The s-Eulerian polynomials have only real roots[END_REF]. By [START_REF] Sloane | On-line encyclopedia of integer sequences[END_REF], that is to say, D + n (x) interlaces x n D + n (1/x). This completes the proof of (ii). 2

Note that the stability of the polynomial (x + 1)A n-1 (x) -nxA n-2 (x) is critical to our approach. In Theorem 2.3, we have determined the stability of (x + 1)A n-1 (x) + kxA n-2 (x) for k ≥ -n. It is natural to consider the possible values of k for which the stability of this polynomial still holds. Let E n be the n-th Euler zigzag number, see [14, A000111], which is the number of up-down permutations of the set [n]. Using the Routh-Hurwitz stability criterion (Theorem 2.4), computer evidence suggests the following conjecture. Conjecture 3.2 For any n ≥ 3, the polynomial (x + 1)A n-1 (x) + kxA n-2 (x) is Hurwitz stable if and only if k > -2E n /E n-1 .

As pointed out by a referee, the Euler zigzag numbers also appeared in a conjecture proposed by Zhang [START_REF] Zhang | On the real-rootedness of the descent polynomials of (n -2)-stack sortable permutations[END_REF]Conjecture 4.1], which states that the polynomial A n-1 (x) + kx A n-3 (x) has all distinct real zeros if and only if k < -n(n -1) or k > -a( n/2 ), where a(n) = E 2n+1 /E 2n-1 . It is desirable to find some connections between these two conjectures.


Fu Liu

On bijections between monotone rooted trees and the comb basis

Keywords: free Lie algebra, bijection, rooted trees, comb bases

Let A be an n-element set. Let L ie2(A) be the multilinear part of the free Lie algebra on A with a pair of compatible Lie brackets, and L ie2(A, i) the subspace of L ie2(A) generated by all the monomials in L ie2(A) with i brackets of one type. The author and Dotsenko-Khoroshkin show that the dimension of L ie2(A, i) is the size of R A,i , the set of rooted trees on A with i decreasing edges. There are three families of bases known for L ie2(A, i) ∶ the comb basis, the Lyndon basis, and the Liu-Lyndon basis.

Recently, González D'León and Wachs, in their study of (co)homology of the poset of weighted partitions (which has close connection to L ie2(A, i)), asked whether there are nice bijections between R A,i and the comb basis or the Lyndon basis. We give a natural definition for "nice bijections", and conjecture that there is a unique nice bijection between R A,i and the comb basis. We show the conjecture is true for the extreme cases where i = 0, n -1.

Résumé. Soit A un ensemble à n éléments. Soit L ie2(A) la partie multilinéaire de l'algèbre de Lie libre sur A avec une paire de crochets de Lie compatibles et L ie2(A, i) le sous-espace de L ie2(A) généré par tous les monômes en L ie2(A) avec i supports d'un même type. L'auteur et Dotsenko-Khoroshkin montrent que la dimension de L ie2(A, i) est la taille de la R A,i , l'ensemble des arbres enracinés sur A avec i arêtes décroissantes. Il y a trois familles de bases connues pour L ie2(A, i) : la base de peigne, la base Lyndon, et la base Liu-Lyndon.

Récemment, Gonzalez, D' Léon et Wachs, dans leur étude de (co)-homologie de la poset des partitions pondérés, ont demandé si il y a des bijections jolies entre R A,i , et la base de peigne ou la base Lyndon. Nous donnons une définition naturelle de "bijection jolie", et un conjecture qu'il y a une seule bijection jolie entre R A,i , et la base de peigne. Nous montrons que la conjecture est vraie pour les cas extrêmes: i = 0, et n -1.

Introduction

Background

Let A = {a 1 < a 2 < ⋯ < a n } be an ordered set and k a field. Let L ie(n) or L ie(A) be the multilinear component of the free Lie algebra on A over k. It is well known that the dimension of L ie(n) is (n -1)!. Feigin considered the free Lie algebra on A equipped with two compatible Lie brackets [⋅, ⋅] and ⟨⋅, ⋅⟩, and Fu Liu its multilinear component which we denote by L ie 2 (n) or L ie 2 (A). Further, he conjectured the dimension of L ie 2 (n) to be n n-1 . His conjecture was proved by the author [START_REF] Liu | Combinatorial bases for multilinear parts of free algebras with two compatible brackets[END_REF] and Dotsenko-Khoroshkin [START_REF] Dotsenko | Character formulas for the operad of two compatible brackets and for the bihamiltonian operad[END_REF][START_REF] Dotsenko | Gröbner bases for operads[END_REF]. In fact, a refinement of Feigin's conjecture was obtained in [START_REF] Liu | Combinatorial bases for multilinear parts of free algebras with two compatible brackets[END_REF] as well: let L ie 2 (n, i) (or L ie 2 (A, i)) be the subspace of L ie 2 (n) (or L ie 2 (A)) generated by all the monomials in L ie 2 (n) (or L ie 2 (A)) with exactly i [⋅, ⋅]'s (and n -1 -i ⟨⋅, ⋅⟩'s), then

dim L ie 2 (A, i) = R A,i , (1.1)
where R A,i is the set of rooted trees on A with i decreasing edges. In [START_REF] Dotsenko | Character formulas for the operad of two compatible brackets and for the bihamiltonian operad[END_REF][START_REF] Dotsenko | Gröbner bases for operads[END_REF], Dotsenko and Khoroshkin use the theory of operads to prove Feigin's conjecture. They also obtain character formulas for the representation of the symmetric groups S n and the SL 2 group in L ie 2 (n). Although (1.1) is not derived directly in their work, it follows from their character formulas and a result of Drake [START_REF] Drake | An inversion theorem for labeled trees and some limits of areas under lattice paths[END_REF].

Another interesting property of L ie(n) is its close connection to the (co)homology of the partition lattice Π n . The symmetric group S n acts naturally on L ie(n), so we can consider L ie(n) an S n -module. At the same time, S n also acts naturally on Π n and this action induces isomorphic representations of S n on the unique nonvanishing reduced simplicial homology Hn-3 ( Πn ) and cohomology Hn-3 ( Πn ) of the order complex ∆( Πn ) of the proper part Πn of Π n . It is a classical result that

Hn-3 ( Πn ) ≅ Sn L ie(n) ⊗ sgn n , (1.2)
where sgn n is the sign representation of S n . Dotsenko and Khoroshkin [START_REF] Dotsenko | Character formulas for the operad of two compatible brackets and for the bihamiltonian operad[END_REF] introduced a weighted version of Π n , denoted by Π w n and called the poset of weighted partitions. (The precise defintion of Π w n is not important to us in this paper.) The weighted partition poset has one unique minimal element, denoted by 0, and n maximal elements, denoted by [n] i for i = 0, 1, . . . , n -1. The (co)homology of maximal open intervals (0, [n] i ) is studied. Vallette [START_REF] Vallette | Homology of generalized partition posets[END_REF] and Dotsenko-Khoroshkin [START_REF] Dotsenko | Gröbner bases for operads[END_REF] show, using the theory of operads, that

Hn-3 ( 0, [n] i ) ≃ Sn L ie 2 (n, i) ⊗ sgn n . (1.3) Since (0, [n] i ) ≅ Πn and L ie 2 (n, i) ≅ L ie(n) when i = 0 or n -1, their result generalizes (1.2).
In [START_REF] González D'león | On the (co)homology of the poset of weighted partitions[END_REF], González D'león and Wachs extend various classical results of Π n to Π w n . In particular, they establish a strong connection between cohomology of open intervals ( 0, [n] i ) and 2v-colored binary trees, which give another proof for (1.3) and provide a way to construct bases for Hn-3 ( 0, [n] i ) from bases for L ie 2 (n, i). They also construct a basis for Hn-3 ( 0, [n] i ) from R A,i .

Questions and results

There are three families of bases known for L ie 2 (A, i) (and thus for Hn-3 ( 0, [n] i ) ) summarized in [START_REF] González D'león | On the (co)homology of the poset of weighted partitions[END_REF] by González D'León and Wachs in their study of (co)homology of weighted partition poset. We list them here, following the notations in [START_REF] González D'león | On the (co)homology of the poset of weighted partitions[END_REF]:

• Comb 2
A,i : Bershtein-Dotsenk-Khoroshkin [START_REF] Bershtein | Quadratic algebras related to the bi-hamiltonian operad[END_REF] introduced a comb basis, for L ie 2 (A, i) generalizing Wachs' comb basis [START_REF] Wachs | On the (co)homology of the partition lattice and the free lie algebra[END_REF] for L ie(A).

• Liu 2

A,i : The author [START_REF] Liu | Combinatorial bases for multilinear parts of free algebras with two compatible brackets[END_REF] introduced a Liu-Lyndon basis for L ie 2 (A, i) generalizing the standard Lyndon basis for L ie(A).

• Lyn 2

A,i : González D'león-Wachs [START_REF] González D'león | On the (co)homology of the poset of weighted partitions[END_REF] constructed another basis for L ie 2 (A, i) that generalizes the standard Lyndon basis. We will refer to it as the Lyndon basis.

Since the dimension of L ie 2 (A, i) is known to be the size of R A,i , we have

R A,i = Comb 2 A,i = Liu 2 A,i = Lyn 2 A,i .
It is thus natural to ask whether one can give bijections between the above four sets. In [START_REF] Liu | Combinatorial bases for multilinear parts of free algebras with two compatible brackets[END_REF], the author gives a bijection between R A,i and Liu A,i . In [START_REF] González D'león | On the free Lie algbra with multiple brackets[END_REF], González D'león constructs a bijection between Comb

≤ i ≤ A -1.
Below is the main result of the paper.

Theorem 1.2 Conjecture 1.1 holds for i = 0 and i = n -1.
We finish this part with a potential consequence of answering González D'león and Wachs' question. In [START_REF] González D'león | On the free Lie algbra with multiple brackets[END_REF], González D'león generalizes L ie 2 (n) to L ie k (n), the multilinear part of the free Lie algebra with k compatible brackets, and introduces a new corresponding poset of weighted partition Π k n that generalizes Π w n . He obtains various dimension formulas for L ie k (n) and generalizations of the comb basis Comb 2

A,i and the Lyndon basis Lyn 2 A,i . Generalizing the techniques in [START_REF] González D'león | On the (co)homology of the poset of weighted partitions[END_REF], he shows these bases also provide bases for cohomology of maximal open intervals of Π k n . However, bases for homology of Π k n are still waiting to be found. One key ingredient used in [START_REF] González D'león | On the (co)homology of the poset of weighted partitions[END_REF] to find a basis for Hn-3

( 0, [n] i ) is the bijection from R A,i to Liu 2
A,i given in [START_REF] Liu | Combinatorial bases for multilinear parts of free algebras with two compatible brackets[END_REF]. Since neither bases for L ie k (n) constructed in [START_REF] González D'león | On the free Lie algbra with multiple brackets[END_REF] is a generalization of Liu 2 A,i , it is hard to generalize the method used for Π w n to Π k n . However, if we are able to find a nice bijection from R A,i to either Comb 2 A,i or Lyn 2 A,i , we can hope to generalize it and find a basis for the homology of maximal open intervals of Π k n .

Rooted trees and the comb basis

In this section, we will introduce the main combinatorial objects that are going to be used in this paper.

Definition 2.1 A tree is a connected acyclic graph. A rooted tree is a tree with one special vertex, which we call it the root of the tree. Let R A be the set of all rooted trees on the n-element set A, i.e., all the rooted trees with n vertices that are labeled by the elements in A.

For any edge {i, j} in a rooted tree, if i is closer to the root than j, we call i the parent of j and j a child of i. Furthermore, if i is the parent of j, we say {i, j} an increasing edge if i < j, and a decreasing edge if i > j. For convenience, we color each increasing edge blue and each decreasing edge red.

Let R A,i be the set of rooted trees on A with i decreasing/blue edges (and n -1 -i increasing/blue edges).

Fu Liu

Note that for any rooted tree in R A,0 , all of its edge are increasing. Thus, we call trees in R A,0 increasing trees. Similarly, we call trees in R A,n-1 decreasing trees.

A monotone tree is either an increasing tree or a decreasing tree.

See Figure 1 for the nine rooted trees in R A with n = 3, where the first two trees on the first row are increasing trees in R A,0 , the last two trees on the first row are decreasing trees in R A,2 , and the five trees on the second row are in R A,1 .

a 1 a 2 a 3 a 1 a 2 a 3 a 3 a 2 a 1 a 3 a 1 a 2 a 1 a 3 a 2 a 2 a 1 a 3 a 2 a 3 a 1 a 2 a 3 a 1 a 3 a 1 a 2 Fig. 1: Rooted trees in R A with n = 3
A vertex in a rooted tree is a leaf if it does not have any children, and is an internal vertex otherwise.

Definition 2.2 A binary tree is an ordered (rooted) tree, where all of its internal vertices have exactly two children.

A 2v-colored binary tree is a binary tree whose internal vertices are colored by red or blue. We denote by BT A the set of all 2v-colored binary trees whose leaves are labeled by A, and by BT A,i the set of all 2v-colored binary trees whose leaves are labeled by A and i of whose internal vertices are red.

See Figure 2 for an example of 2v-colored binary tree. A labeled binary tree is normalized if the leftmost leaf of each subtree has the smallest label in the subtree.

Definition 2.3 A tree in BT

A is a 2v-colored comb if it is normalized and satisfies the following coloring restriction: for each internal vertex i whose right child j is not a leaf, i is colored red and j is colored blue.

We denote by Comb 2

A the set of all 2v-colored combs in BT A , and by Comb 2 A,i the set of all 2v-colored combs in BT A,i .

See Figure 3 for all the nine combs in Comb 2

A with n = 3, where the first two trees on the first row are in Comb 2 A,0 , the last two trees on the first row are in Comb 2 A,2 , and the five trees on the second row are in

Comb 2 A,1 . a 1 a 2 a 3 ⟨⟨a 1 , a 2 ⟩, a 3 ⟩ a 1 a 3 a 2 ⟨⟨a 1 , a 3 ⟩, a 2 ⟩ a 1 a 2 a 3 [[a 1 , a 2 ], a 3 ] 1 a 3 a 2 [[a 1 , a 3 ], a 2 ] a 1 a 3 a 2 [⟨a 1 , a 3 ⟩, a 2 ] a 1 a 2 a 3 ⟨[a 1 , a 2 ], a 3 ⟩ a 2 a 3 a 1 [a 1 , ⟨a 2 , a 3 ⟩] a 1 a 3 a 2 ⟨[a 1 , a 3 ], a2⟩ a 1 a 2 a 3 [⟨a 1 , a 2 ⟩, a 3 ] Fig. 3: 2v-colored combs in Comb 2 A with n = 3
There is a canonical bijection between BT A,i and all the monomials in L ie 2 (A, i) ∶ given a 2v-colored binary tree in BT A,i , each leaf denotes a letter in A, and we can construct a monomial in L ie 2 (A, i) recursively by interpreting each internal vertex as a bracket of the left and right subtrees, with red vertices corresponding to [⋅, ⋅] and blue vertices corresponding to ⟨⋅, ⋅⟩. For example, in Figure 3, each comb corresponds to the monomial shown below it. Therefore, we can consider that L ie 2 (A, i) is spanned by elements of BT A,i and use BT A,i to describe bases of L ie 2 (A).

Bershtein, Dotsenko and Khoroshkin show in [START_REF] Bershtein | Quadratic algebras related to the bi-hamiltonian operad[END_REF] that Comb 2 A,i , considered as a set of monomials, is a basis for L ie 2 (A, i), and we call it the comb basis.

From now on, we will always consider BT A and Comb 2 A as sets of monomials of L ie 2 (A). (We only introduce the binary tree terminology because it is easier to be used to describe the combs.)

Good-pair bijections

In this section, we will define good-pair bijections, which we consider to be "nice" bijections, and reduce Conjecture 1.1 to a new conjecture (Conjecture 3.9). We will also explain why our definition of "good-pair bijection" is natural. Definition 3.1 We say m ∈ BT A and G ∈ R A form a good pair if one of the following is satisfied:

(i) A = 1.
(ii) Suppose A ≥ 2 and m = {m 1 , m 2 }, where {⋅, ⋅} = [⋅, ⋅] or ⟨⋅, ⋅⟩. There exists an edge e of G such that:

Fu Liu

1. e has the same color as {⋅, ⋅}, i.e., e is red if {⋅, ⋅} = [⋅, ⋅] and e is blue if {⋅, ⋅} = ⟨⋅, ⋅⟩;

2. By removing e from G, we obtain two rooted trees G 1 and G 2 such that m i and G i form a good pair for each i.

It follows immediately from the definition that if m ∈ BT A and G ∈ R A form a good pair, then m ∈ BT A,i and G ∈ R A,i for some i.

Example 3.2 Below we give all the good pairs between elements in R A and BT A when A = 2. Example 3.3 In Figure 4, G 1 and G 2 are the (only) two rooted trees in R A,0 , and m 1 and m 2 are two monomials in BT A,0 . We summarize the good-pair relations between {m 1 , m 2 } and {G 1 , G 2 } below.

The rooted tree

a 1 a 2 a 3 m 1 = ⟨⟨a 1 , a 2 ⟩, a 3 ⟩ a 1 a 3 a 2 m 2 = ⟨⟨a 1 , a 3 ⟩, a 2 ⟩ a 1 a 2 a 3 G 1 a 1 a 2 a 3 G 2
Fig. 4:

• G 1 forms a good pair with m 1 , but not with m 2 . (One sees that in order to be a good pair with m 2 , a rooted tree has to have a blue edge connecting a 1 and a 3 . However, G 1 does not have such an edge.)

• G 2 forms a good pair with both m 1 and m 2 .

Definition 3.4 Given B ⊆ BT A,i a basis for L ie 2 (A, i), we say a bijection ψ ∶ R A,i → B is a good-pair bijection if ψ(G) and G form a good pair for each G ∈ R A,i .

Example 3.5 Suppose n = 3. Let m 1 , m 2 , G 1 and G 2 be as in Figure 4. Note that

{m 1 , m 2 } = Comb 2 A,0
is the comb basis for L ie 2 (A, i).

Clearly, the map that maps G i to m i for i = 1, 2 is a good-pair bijection. Furthermore, we observe that it is the unique good-pair bijection from R A,0 to B.

Because of the observation in the above example, we modify question of González D'León and Wachs: Question 3.6 For each of the three known bases Comb 2 A,i , Liu 2 A,i , and Lyn 2 A,i , does good-pair bijection exist? If so, is it unique?

The following lemma gives one way to prove both the existence and uniqueness of a good-pair bijection.

Fu Liu

In [START_REF] González D'león | On the (co)homology of the poset of weighted partitions[END_REF], González D'León and Wachs associate cT , a maximal chain in ( 0, [n] i ), to each T ∈ BT A,i . This association provides a connection between bases for L ie 2 (A, i) and bases for Hn-3 (( 0, [n] i )). More precisely, for any basis B ⊆ BT A,i of L ie 2 (A, i), {c T T ∈ B} is a basis for Hn-3 (( 0, [n] i )). They also associate ρ G , a fundamental cycle of the spherical complex ∆( ΠG ), to each G ∈ R A,i , and show that {ρ G G ∈ R A,i is a basis for Hn-3 (( 0, [n] i )). Also, when the (co)homology is defined in [START_REF] González D'león | On the (co)homology of the poset of weighted partitions[END_REF], the chain and cochain spaces have been identified using the natural bases. This identification is given by the bilinear form ⟪⋅, ⋅⟫. Then we have that ⟪ρ G , cT ⟫ ≠ 0 if and only if T and G form a good pair.

Therefore, one sees that "good-pair" really is a natural way to define a "nice" bijection from R A,i to a basis of L ie 2 (A, i). In particular, because of its connection to bilinear form defined between homology and cohomology in [START_REF] González D'león | On the (co)homology of the poset of weighted partitions[END_REF], like we've discussed in the introduction, if one is able to find a good-pair bijection from R A,i to either Comb 2 A,i or Lyn 2 A,i , it is very likely to be generalized and be used to find a basis for the homology of maximal open intervals of π k n introduced by González D'León.

4 The unique bijection between R A,0 and Comb 2 A,0

In this section, we will show our conjectures are true for i = 0. Since all the trees in R A,0 are increasing trees, we write R A,0 as R i A . The main result of this section is the following: Theorem 4.1 Conjecture 3.9 holds for i = 0. Hence, Conjecture 1.1 holds for i = 0.

Observation 4.2 We see that Comb 2

A,0 consists of all monomials of the form

⟨⟨⋯⟨⟨a 1 , a i2 ⟩, a i3 ⟩, ⋯, a in-1 ⟩, a in ⟩, (4.1)
where i 2 i 3 ⋯ i n-1 i n is a permutation on {2, 3, . . . , n}.

A good-pair bijection

We will first construct a bijection from R i A to Comb 2 A,0 and show it is a good-pair bijection. We need a preliminary definition. Definition 4.3 Let A ≥ 2. For each G ∈ R i A , the cutting path, the cutting edge, and the cutting node of G, denoted by CP(G), CE(G), and CN(G) are defined as below:

Let v 0 ∶= a 1 be the root and for each i ≥ 0, if v i is not a leaf, let v i+1 be the smallest child of v

i . Suppose v k is a leaf. Then let CP(G) ∶= v 0 -v 1 -v 2 -⋯ -v k ,
and let CE(G) ∶= {v k-1 , v k } be the last edge in the cutting path, and CN(G) ∶= v k be the leaf in the path.

Now we are ready to define the desired bijection between R i A and Comb

2 A,0 . Definition 4.4 We define a map ϕ A ∶ R i A → Comb 2 A,0 recursively in the following way. Let G ∈ R i A . (i) If A = {a} has only one element, we define ϕ A (G) ∶= a. (ii) Otherwise, if A ≥ 2, we define ϕ A (G) ∶= ⟨ϕ A∖{CN (G)} (G ∖ CN(G)), CN(G)⟩,
where G ∖ CN(G) is the tree obtained from G by removing the leaf CN(G) and its adjacent edge

CE(G), so it is in R i A∖CN(G) .
When there is no confusion of the set A, we will omit the subscript A from ϕ A and just write ϕ.

It is easy to see that ϕ(G) is always in the form of (4.1). Hence, the map ϕ is well-defined.

Example 4.5 Let G 1 and G 2 be the two rooted trees in Figure 4. Then

CP(G 1 ) = a 1 -a 2 -a 3 and ϕ(G 1 ) = ⟨⟨a 1 , a 2 ⟩, a 3 ⟩; CP(G 2 ) = a 1 -a 2 and 2 ) = ⟨⟨a 1 , a 3 ⟩, a 2 ⟩.
Proposition 4.6 ϕ is a good-pair bijection from R i A to Comb 2 A,0 . Since it is clear that G and ϕ(G) form a good pair for each G ∈ R i A , in order to prove Proposition 4.6, we only need to construct an inverse map ϕ -1 from Comb 2 A,0 to R i A . Definition 4.7 Suppose A ≥ 2. Let a be an element of A that is not a 1 , and let

A ′ = A ∖ {a}. Suppose G ′ ∈ R i A ′ , with CP(G ′ ) = v 0 -v 1 -v 2 -⋯ -v k ,

and let

∶= max{i v i < a}. (So we have a 1 = v 0 < v 1 < ⋯ < v < a < v +1 < ⋯ < v k .) We define the i-merge of G ′ and a, denoted by G ′ ◁a, to be the increasing tree obtained by connecting a to the vertex v of G ′ . A (m) ∶= ((⋯((a 1 ◁a i2 )◁a i3 )◁⋯◁a in-1 )◁a in ).

It is easy to verify that ϕ A and ϕ -1 A are inverse to each other. Therefore, we complete the proof of Proposition 4.6.

An ordering on cutting paths

We will define an ordering on sequences that are made from the ordered set A. Definition 4.9 Suppose α = α 1 -α 2 -⋯ -α s and β = β 1 -β 2 -⋯-β t , where α i , β j ∈ A. We write α < mlex β if one of the following is satisfied: a) There exists 1 ≤ r ≤ min(s, t) such that α i = β i for each i < r and α r < β r . b) β is a proper subsequence of α; that is, t < s and α i = β i for each i ≤ t.

We call the above ordering the modified lex(icographical) order. (Note that if we replace condition b) with "α is a proper subsequence of β", we recover the regular lex order.) One can verify < mlex is a well-defined ordering.

3 Fig. 2 :

 32 Fig. 2: Example of a tree in BT A,2 with n = 5

a 1 a 2 2 a 1

 221 forms a good pair with ⟨a , a 2 ⟩ and ⟨a 2 , a 1 ⟩.The rooted tree a forms a good pair with [a 1 , a 2 ] and [a 2 , a 1 ].

Definition 4 . 8

 48 We define a map ϕ-1 A ∶ Comb 2 A,0 → R i A in the following way. Let m ∈ Comb 2 A,0 .(i) If A = {a} has only one element, we define ϕ -1 A (m) ∶= a. (ii) Otherwise, Suppose A ≥ 2 and m is in the form of (4.1). Let ϕ -1

  The motivation of this paper is to answer their question.Before we can answer the question of González D'león and Wachs, we need to clarify what bijections are "nice". We give such a definition in Section 3, where good-pair bijections are defined. With this definition, we conjecture the following: Conjecture 1.1 There exists a unique good-pair bijection from R A,i → Comb 2 A,i for any nonempty finite ordered set A and 0

	2 A,i and
	Lyn 2 n,i . Given these results, González D'león and Wachs ask whether there are nice bijections between
	R A,i and Comb 2 A,i or Lyn 2 A,i [6, Remark 5.11].

† Fu Liu is partially supported by NSF grant DMS-1265702.

1365-8050

Lemma 3.7 Let B ⊆ BT A,i be a basis for L ie 2 (A, i). There exist a total ordering on R A,i : G 1 , G 2 , . . . and a total ordering on B ∶ b 1 , b 2 , . . . such that (i) b i and G i form a good pair for each i;

(ii) b i and G j does not form a good pair unless i ≤ j.

Then there is a unique good-pair bijection from R A,i to B.

Proof: mapping G i to b i for each i gives a good-pair bijection. On the other hand, given a good-pair bijection ψ, since G 1 is good pair with nothing other than b 1 , ψ has to map G 1 to b 1 . As a result, it is forced to map G 2 to b 2 , and so on. Hence, the good-pair bijection is unique. ◻

In fact, in [START_REF] Liu | Combinatorial bases for multilinear parts of free algebras with two compatible brackets[END_REF], the author shows that the hypothesis of Lemma 3.7 is for the Liu-Lyndon basis Liu 2

A,i . Hence, we immediately have the following fact: Fact 3.8 There exists a unique good-pair bijection from R A,i to Liu 2

A,i and it is the one constructed in [START_REF] Liu | Combinatorial bases for multilinear parts of free algebras with two compatible brackets[END_REF].

Therefore, Question 3.6 is only open for the comb basis Comb 2

A,i and the Lyndon basis Lyn 2 A,i . After checking small examples of comb bases, we conjecture that the hypothesis of Lemma 3.7 holds for the comb basis. Conjecture 3.9 There exist a total ordering on R A,i : G 1 , G 2 , . . . and a total ordering on Comb 2 A,i ∶ m 1 , m 2 , . . . such that (i) m i and G i form a good pair for each i;

(ii) m i and G j does not form a good pair unless i ≤ j.

By Lemma 3.7, Conjecture 3.9 implies Conjecture 1.1.

Example 3.10 We've verified that Conjecture 3.9 is true for n ≤ 4. Hence, Conjecture 1.1 holds for n ≤ 3.

The situations for n = 1 and 2 are trivial. When n = 3, we order R A,i and Comb A,i as they are shown in Figures 1 and3. One checks that the orderings satisfying conditions (i) and (ii) of Conjecture 3.9.

There are 4 3 = 64 rooted trees and combs when n = 4. So we omit the details here.

Remark 3.11 For the Lyndon basis Lyn 2 A,i , we've checked that the hypothesis of Lemma 3.7 holds for n up to 3. However, we have not had chance to check the case for n = 4. Since for n ≤ 3, the size of each basis is very small, we do not think we have enough data to make similar conjectures.

Why good-pair?

We finish this section with an explanation of why we consider good-pair bijections are nice bijections. In fact, the definition of "good pair" has close connection to both work in [START_REF] Liu | Combinatorial bases for multilinear parts of free algebras with two compatible brackets[END_REF] and [START_REF] González D'león | On the (co)homology of the poset of weighted partitions[END_REF].

In [START_REF] Liu | Combinatorial bases for multilinear parts of free algebras with two compatible brackets[END_REF], the author constructs a monomial b G from each G ∈ R A,i and shows that Liu 2

One main technique used in the proof is that a complementary space E il 2 (A) is introduced where rooted trees are elements of E il 2 (A), and a pairing between L ie 2 (A) and E il 2 (A) are defined and shown to be perfect. Then the pairing of b G and G ′ is nonzero if and only if b G and G ′ form a good pair, for any G, G ′ ∈ R A,i .

Fu Liu

Example 4.10 Let G 1 and G 2 be the two rooted trees in Figure 4. Then

We have the following two important lemmas stating that the i-merge operation ◁ minimizes the cutting path, and preserving the orderings of cutting paths. Lemma 4.11 Suppose A ≥ 2. Let a be an element of A that is not a 1 , and let

A is obtained by connecting a to a vertex of G ′ . Then we have the followings:

Hence, we always have CP(G ′ ◁a) ≤ mlex CP(G).

Proof: Suppose CP(G ′ ) and are given as in Definition 4.7. Then

Thus, a) follows immediately from the definition of the modified lex order. Suppose G ≠ (G ′ ◁a). Let v be the vertex in G ′ that a is connected to. Then v ≠ v . If v ≠ v i for any i, it is clear that we have CP(G) = CP(G ′ ). Suppose v = v i for some i ≠ . Since a < v i for i > and {v, a} is an increasing edge, we must have that i < . Then one checks that CP(G) = CP(G ′ ). ◻ Lemma 4.12 Suppose A ≥ 2. Let a be an element of A that is not a 1 , and let

, by the definition of i-merge, it's clear that CP(G

and let ∶= max{i α i < a}.

Then one of the conditions in Definition 4.9 is satisfied. Suppose condition b) of Definition 4.9 is satisfied; that is, CP(G 2 ) is a proper subsequence of CP(G 1 ). Then

Suppose condition a) of Definition 4.9 is satisfied. Then

Proof: We prove by induction on A . If A = 1, the statement is trivially true. Assume n ≥ 2 and the statement holds for A with cardinality n -1. We will show the statement is true for A = n. Suppose m is in the form of (4.1). Let

Since m and G form a good pair. There exist G ′ ∈ R i A ′ such that G is obtained from G by attaching a to a vertex of G, and m ′ and G ′ form a good pair. By induction hypothesis, we have that CP(ϕ -1 (m ′ )) ≤ mlex CP(G ′ ).

Note that

)◁a, and G By Lemmas 4.12 and 4.11, we have

We give an ordering on Comb 2 A,0 accordingly by letting

First, because ϕ is a good-pair bijection, we clearly have that m i and G i form a good pair for each i. Suppose m i and G j form a good pair. Then by Corollary 4.13, we have

By the construction of ≺, we have G i ⪯ G j , which means i ≤ j.. ◻

5 The unique bijection between R A,n-1 and Comb 2

A,n-1

The main result of this section is that our conjectures are true for i = n -1.

Theorem 5.1 Conjecture 3.9 holds for i = n -1. Hence, Conjecture 1.1 holds for i = n -1.

The proof is very similar to what we give for the cases where i = 0 in the last section, but with a slightly complicated construction. We omit the proof from this extended abstract.