Samuele Giraudo

OPERADS FROM POSETS AND KOSZUL DUALITY

Keywords: 2010 Mathematics Subject Classification. 05E99, 05C05, 06A11, 18D50 Tree, Rewrite rule, Poset, Operad, Koszul duality, Koszul operad

We introduce a functor As from the category of posets to the category of nonsymmetric binary and quadratic operads, establishing a new connection between these two categories. Each operad obtained by the construction As provides a generalization of the associative operad because all of its generating operations are associative. This construction has a very singular property: the operads obtained from As are almost never basic. Besides, the properties of the obtained operads, such as Koszulity, basicity, associative elements, realization, and dimensions, depend on combinatorial properties of the starting posets. Among others, we show that the property of being a forest for the Hasse diagram of the starting poset implies that the obtained operad is Koszul. Moreover, we show that the construction As restricted to a certain family of posets with Hasse diagrams satisfying some combinatorial properties is closed under Koszul duality.

Introduction

Very recent examples show that the theory of operads, since its introduction [START_REF] May | The Geometry of Iterated Loop Spaces[END_REF]BV73] in the 1970s, is developing year after year many fruitful connections with combinatorics. In fact, there are at least three important instances to warrant this assertion. First, the Hilbert series of a Koszul operad and its Koszul dual are related by an inversion operation on series [START_REF] Ginzburg | Koszul duality for operads[END_REF][START_REF] Bergström | Inversion of series and the cohomology of the moduli spaces M δ 0,n . In Motives, quantum field theory, and pseudodifferential operators[END_REF], a classical combinatorial operation. Moreover, the Koszulity property for operads is strongly related to the theory of rewrite rules on trees, this last providing a sufficient combinatorial condition to establish that an operad is Koszul [START_REF] Hoffbeck | A Poincaré-Birkhoff-Witt criterion for Koszul operads[END_REF]DK10,[START_REF] Loday | Algebraic Operads[END_REF]. Finally, another strategy to prove that an operad is Koszul consists in constructing a family of posets from an operad [MY91], so that the Koszulity of the considered operad is a consequence of a combinatorial property of the posets of the obtained family [Val07] (see also [START_REF] Loday | Algebraic Operads[END_REF]).

Moreover, by endowing a set of combinatorial objects with an operad structure, the theory of operads helps to establish combinatorial properties of its objects and leads to new ways of understanding it. Indeed, since operads are algebraic structures modeling the composition of operators, operads on combinatorial objects allow to decompose objects into elementary pieces. This may potentially bring and highlight combinatorial properties. For instance, several operads on various sorts of trees emphasize some properties of trees [Cha08], the definition of an operad structure on a sort of noncrossing configurations in polygons leads to a formula for their enumeration [CG14], and the definition of several operads on combinatorial objects such as Motzkin paths and directed animals leads to see these as gluings of small objects [Gir15a] and to derive properties.

On the other side, purely combinatorial observations lead to algebraic properties on operads. For instance, computations in the dendriform operad, introduced by Loday [Lod01], can be performed by considering intervals of the Tamari order [START_REF] Tamari | The algebra of bracketings and their enumeration[END_REF] (see [START_REF] Loday | Order structure on the algebra of permutations and of planar binary trees[END_REF]). Furthermore, pre-Lie algebras, introduced independently by Vinberg [START_REF] Vinberg | The theory of homogeneous convex cones[END_REF] and by Gerstenhaber [START_REF] Gerstenhaber | The cohomology structure of an associative ring[END_REF], form an important class of algebras appearing among others in the study of homogeneous cones and affine manifolds. The pre-Lie operad, defined by Chapoton and Livernet [CL01], encodes the category of pre-Lie algebras. This operad involves rooted trees and its partial composition is described by means of tree grafts. The existence of this operad and of its combinatorial description in terms of rooted trees lead to the construction of free pre-Lie algebras. This work is devoted to enrich these connections between operads and combinatorics by establishing a new link between posets and nonsymmetric operads by means of a construction associating a nonsymmetric operad As(Q), called Q-associative operad, with any finite poset Q. This construction is a functor As from the category of finite posets to the category of nonsymmetric binary and quadratic operads. The will to generalize two families of operads Koszul dual to each other, constructed in a previous work [Gir15b], is the first impetus of this paper. The operads of these families, called multiassociative operads and dual multiassociative operads, are respectively denoted by As γ and As ! γ , and depend on a nonnegative integer parameter γ. In this present work, we retrieve As γ by applying the construction As on the total order on a set of γ elements and we retrieve As ! γ by applying the construction As on the trivial order on the same set.

Let us describe some main properties of As. First, each operad obtained by our construction provides a generalization of the associative operad since all its generating operations are associative. Besides, many combinatorial properties of the starting poset Q lead to algebraic properties for As(Q) (see Table 1). For instance, when Q is a forest ( 1. Summary of the properties satisfied by a poset Q implying properties for the operad As(Q). Note that any trivial poset is also a thin forest poset, and that a thin forest poset is also a forest poset. In particular, if Q is a trivial poset, As(Q) has all properties mentioned in the middle column.

no element of Q covers two different elements), As(Q) is a Koszul operad. Moreover, when Q is not a trivial poset, As(Q) is not a basic operad (property defined in [Val07]). This last property seems to be interesting since almost all common operads are basic, such as the associative operad or the diassociative operad [Lod01] (see additionally [Zin12] and the references therein for a census of the most famous operads and their main properties). This gives to our construction a very unique flavor.

The further study of the operads obtained by the construction As is driven by computer exploration. Indeed, computer experiments bring us the observation that some operads obtained by the construction As are Koszul dual to each other. This observation raises several questions. The first one consists in describing the family of posets such that the construction As restrained to this family is closed under Koszul duality. The second one consists in defining an operation ⊥ on this family of posets such that for any poset Q of this family, As(Q ⊥ ) is isomorphic to the Koszul dual As(Q) ! of As(Q). The last one relies on an expression of an explicit isomorphism between As(Q) ! and As(Q ⊥ ). We answer all these questions in this work, forming its main result. This paper and the presented results are organized as follows. Section 1 contains basic definitions about posets, rewrite rules on trees, and operads. We state therein some lemmas used in the sequel about these objects. Most important are Lemma 1.2.1 establishing a criterion to prove that a rewrite rule is confluent, and Lemma 1.3.1 establishing a criterion to prove that an operad is Koszul. These results are already known: the first one belongs to folklore and we provide a proof for it, and the second one is a consequence of works of Dotsenko and Khoroshkin [DK10], and Hoffbeck [START_REF] Hoffbeck | A Poincaré-Birkhoff-Witt criterion for Koszul operads[END_REF].

Section 2 is concerned with the description of the construction As and the first general properties of the obtained operads. We begin by showing that As is functorial (Theorem 2.1.3).

Next, for any poset Q, we describe the associative elements of As(Q) (Proposition 2.2.2) and show that As(Q) is basic if and only if Q is a trivial poset (Proposition 2.2.3). We end this section by describing algebras over the operads As(Q), called Q-associative algebras, and by introducing a notion of units for these algebras accompanied with certain properties (Proposition 2.3.1).

In Section 3, we focus on the case where the poset Q as input of the construction As is a forest poset. We show that in this case, As(Q) is a Koszul operad (Theorem 3.1.5) and derive some consequences. In particular, we give a functional equation for the Hilbert series of As(Q) (Proposition 3.2.1) and provide a combinatorial realization of As(Q) involving Schröder trees [START_REF] Stanley | Enumerative Combinatorics[END_REF] endowed with a labeling satisfying some constraints (Theorem 3.2.5). We next use this realization of As(Q) to describe free algebras over As(Q) over one generator. We end this section by establishing two presentations for the Koszul dual of As(Q) (Propositions 3.3.1 and 3.3.3). This work ends by introducing in Section 4 a class of posets whose elements are called thin forest posets. The construction As restricted to this class of posets has the property to be closed under Koszul duality. This property relies upon an involution ⊥ on thin forest posets. We show (Theorem 4.2.2) that if Q is a thin forest poset, there is a thin forest poset Q ⊥ such that As(Q) ! and As(Q ⊥ ) are isomorphic. This addresses the questions previously raised.

Elementary definitions and lemmas

In this preliminary section, basic notions about posets, trees, and operads are recalled. In particular, we describe the notions of patterns in posets and pattern avoidance, rewrite rules on trees, and Koszulity of operads. Besides, this section contains four lemmas, used further in the text.

1.1. Posets and poset patterns. Unless otherwise specified, we shall use in the sequel the standard terminology about posets [START_REF] Stanley | Enumerative Combinatorics[END_REF]. For the sake of completeness, let us recall the most important definitions and set our notations.

1.1.1. Posets. Let (Q, Q ) be a poset. We denote by ≺ Q the strict order relation obtained from Q and by Q the complementary binary relation of Q . We denote by ↑ Q the binary partial operation min on Q. All posets considered in this work are finite, so that Q is a finite set and has a cardinality, called size of Q.

A chain of Q is a subset {c 1 , . . . , c } of Q such that c i ≺ Q c i+1 for all i ∈ [ -1]. An antichain of Q is a subset {a 1 , . . . , a } of Q such that a i Q a j implies i = j for all i, j ∈ [ ]. If a and c are two elements of Q such that a Q c, the interval [a, c] is the set {b ∈ Q : a Q b Q c}. The number of intervals of Q is denoted by int(Q). An order filter of Q is a subset F of Q such that for all a ∈ F and all b ∈ Q satisfying a Q b, b is in F. A subposet of Q is a subset Q of Q endowed with the order relation of Q restricted to Q .
We shall define posets Q by drawing Hasse diagrams, where minimal elements are drawn uppermost and vertices are labeled by the elements of Q. For instance, the Hasse diagram

1 2 3 4 5 6 , (1.1.1)
denotes the poset ([6], ) satisfying among others 3 5 and 2 6.

Let (Q 1 , Q1 ) and (Q 2 , Q1 ) be two posets. A morphism of posets is a map φ : Q 1 → Q 2 such that x Q1 y implies φ(x) Q2 φ(y). Lemma 1.1.1. Let Q 1 and Q 2 be two posets and φ : Q 1 → Q 2 be a morphism of posets. Then, for all comparable elements a and b of Q 1 , φ (a ↑ Q1 b) = φ(a) ↑ Q2 φ(b). (1.1.2)
This easy property pointed out by Lemma 1.1.1 intervenes later to show that our construction from posets to operads is functorial.

1.1.2. Poset patterns. Let (Q 1 , Q1
) and (Q 2 , Q1 ) be two posets. We say that Q 1 admits an occurrence of (the pattern) Q 2 if there is an isomorphism of posets φ :

Q 1 → Q 2 where Q 1 is a subposet of Q 1 . Conversely, we say that Q 1 avoids Q 2 if there is no occurrence of Q 2 in Q 1 .
Since only the isomorphism class of a pattern is important to say if a poset admits an occurrence of it, we shall draw unlabeled Hasse diagrams to specify patterns. For instance, the poset

Q := 1 2 3 4 5 (1.1.3)
admits an occurrence of the pattern We call forest poset any poset avoiding the pattern . In other words, a forest poset is a poset for which its Hasse diagram is a forest of rooted trees (where roots are minimal elements).

(1.1.4) since 1 Q 3, 1 Q 4, 3 Q 5,
Lemma 1.1.2. Let Q be a forest poset and a, b, and c be three elements of Q such that a and b are comparable and b and c are comparable. Then, a

↑ Q b ↑ Q c is a well-defined element of Q.
This easy property pointed out by Lemma 1.1.2 is crucial to establish the Koszulity of some operads constructed further.

1.2. Trees and rewrite rules. Unless otherwise specified, we use in the sequel the standard terminology (i.e., node, edge, root, parent, child, ancestor, etc.) about planar rooted trees [START_REF] Knuth | The Art of Computer Programming, volume 1: Fundamental Algorithms[END_REF]. For the sake of completeness, let us recall the most important definitions and set our notations. 1.2.1. Trees. Let t be a planar rooted tree. The arity of a node of t is its number of children. An internal node (resp. a leaf) of t is a node with a nonzero (resp. null) arity. Internal nodes can be labeled, that is, each internal node of a tree is associated with an element of a certain set. Given an internal node x of t, due to the planarity of t, the children of x are totally ordered from left to right and are thus indexed from 1 to the arity of x. Similarly, the leaves of t are totally ordered from left to right and thus are indexed from 1 to the number of its leaves. In our graphical representations, each planar rooted tree is depicted so that its root is the uppermost node. Since we consider in the sequel only planar rooted trees, we shall call these simply trees.

Let t be a tree. A tree s is a bottom subtree of t if there exists a node x of t such that the tree consisting in the nodes of t having x as ancestor is s. A tree s is a top subtree of t if s can be obtained from t by replacing certain of nodes of t by leaves and by forgetting their descendants. A tree s is a middle subtree of t if s is a top subtree of a bottom subtree of t. The position pos t (x) of a node x of t is the word of positive integers recursively defined by pos t (x) := if x is the root of t and otherwise pos t (x) := i pos s (x), where x is in the bottom subtree s rooted at the ith child of the root of t.

If t is a labeled tree wherein all internal nodes have exactly two children, the infix reading word of t is the word obtained recursively by concatenating the infix reading word of the bottom subtree of t rooted at the first child of its root, the label of the root of t, and the infix reading word of the bottom subtree of t rooted at the second child of its root. Let t and s be two trees. An occurrence of (the pattern) s in t is a position u of a node x of t such that s is a middle subtree of t rooted at x. Conversely, we say that t avoids s if there is no occurrence of s in t. Let s be a tree with the same number of leaves as s and u be an occurrence of s in t. The replacement of the occurrence u of s by s in t is the tree obtained by replacing the middle subtree of t rooted at a node of position u equal to s by s . 1.2.2. Rewrite rules. Let S be a set of trees. A rewrite rule on S is a binary relation → on S whenever for all trees s and s of S, s → s only if s and s have the same number of leaves. We say that a tree t is rewritable in one step by → into t if there exist two trees s and s satisfying s → s and t admits an occurrence u of s such that the tree obtained by replacing the occurrence u of s by s in t is t . We denote by t → t this property, so that → is a binary relation on S. When t = t or when there exists a sequence of trees (t 1 , . . . , We shall use the standard terminology (terminating, normal form, confluent, convergent, critical pair, etc.) about rewrite rules [BN98]. Let us recall the most important definitions. Let → be a rewrite rule. The degree of → is the maximal number of internal nodes of the trees appearing as left members of → . Besides, → is terminating if there is no infinite chain t → t 1 → t 2 → • • • . In this case, any tree t of S that that cannot be rewritten by → is a normal form for → . We say that → is confluent if for any trees t, r 1 , and r 2 such that t * → r 1 and t * → r 2 , there exists a tree t such that r 1 * → t and r 2 * → t . We call critical tree of → any tree t such that there exist two different trees r 1 and r 2 satisfying t → r 1 and t → r 2 . In this case, the pair {r 1 , r 2 } is a critical pair of → associated with t. Moreover, the critical pair {r 1 , r 2 } is joinable if there exists a tree t such that r 1 * → t and r 2 * → t . By the diamond lemma [START_REF] Newman | On theories with a combinatorial definition of "equivalence[END_REF], when → is terminating and when for any tree t, all critical pairs associated with t are joinable, → is confluent. When → is both terminating and confluent, we say that → is convergent. Lemma 1.2.1. Let → be a terminating rewrite rule of degree . Then, → is confluent if and only if all critical pairs of → consisting in trees with 2 -1 internal nodes or less are joinable.

t k-1 ) with k 1 such that t → t 1 → • • • → t k-1 → t ,
Proof. If → is confluent, by definition of the confluence, all critical pairs of → are joinable. In particular, critical pairs of trees with 2 -1 internal nodes of less are joinable.

Conversely, assume that all critical pairs of trees with 2 -1 internal nodes of less are joinable. Let t be a critical tree of → and {r 1 , r 2 } be a critical pair associated with t. We have thus t → r 1 and t → r 2 . By definition of → , there are four trees t 1 , r 1 , t 2 , and r 2 such that t 1 → r 1 , t 2 → r 2 , and r 1 (resp. r 2 ) is obtained by replacing an occurrence u 1 (resp. u 2 ) of t 1 (resp. t 2 ) by r 1 (resp. r 2 ) in t. We have now two cases to consider, depending on the positions u 1 and u 2 of t 1 and t 2 in t.

Case 1. If the occurrences of t 1 and t 2 at positions u 1 and u 2 in t do not share any internal node of t, r 1 (resp. r 2 ) admits the considered occurrence of t 2 (resp. t 1 ). For these reasons, let t be the tree obtained by replacing the considered occurrence of t 2 by r 2 in r 1 . Equivalently, since the considered occurrences of t 1 and t 2 do not overlap in t, t is the tree obtained by replacing the considered occurrence of t 1 by r 1 in r 2 . Thereby, we have r 1 → t and r 2 → t , showing that the critical pair {r 1 , r 2 } is joinable.

Case 2. Otherwise, the occurrences of t 1 and t 2 at positions u 1 and u 2 in t share at least one internal node of t. Denote by s the middle subtree of t consisting in the smallest number of internal nodes such that all the internal nodes of the considered occurrences of t 1 and t 2 in t are in s. Let s 1 be the tree obtained by replacing the considered occurrence of t 1 by r 1 in s and let s 2 be the tree obtained by replacing the considered occurrence of t 2 by r 2 in s. Since the occurrences of t 1 and t 2 overlap in t, by the minimality of the number of nodes of s, s has at most 2 -1 internal nodes. Now, since we have s → s 1 and s → s 2 , s is a critical tree of → and {s 1 , s 2 } is a critical pair associated with s. By hypothesis, {s 1 , s 2 } is joinable, so that there is a tree s such that s 1 * → s and s 2 * → s . By setting t as the tree obtained by replacing the considered occurrence of s by s in t, we finally have r 1 * → t and r 2 * → t , showing that {r 1 , r 2 } is joinable.

We have shown that all critical pairs of → are joinable. Since → is terminating, this implies by the diamond lemma [START_REF] Newman | On theories with a combinatorial definition of "equivalence[END_REF] that → is a confluent rewrite rule. Lemma 1.2.1 provides a criterion to prove that a terminating rewrite rule → is confluent by considering only critical trees and associated critical pairs with a bounded number of internal nodes. We shall work with rewrite rules arising in the context of quadratic operads, and thus with degree 2. In this case, we will consider only critical trees with at most three internal nodes.

1.3. Operads and Koszulity. We adopt most of notations and conventions of [START_REF] Loday | Algebraic Operads[END_REF] about operads. For the sake of completeness, we recall here the elementary notions about operads employed thereafter.

Nonsymmetric operads.

A nonsymmetric operad in the category of vector spaces, or a nonsymmetric operad for short, is a graded vector space O := n 1 O(n) together with linear maps

• i : O(n) ⊗ O(m) → O(n + m -1), n, m 1, i ∈ [n], (1.3.1)
called partial compositions, and a distinguished element 1 ∈ O(1), the unit of O. This data has to satisfy the three relations

(x • i y) • i+j-1 z = x • i (y • j z), x ∈ O(n), y ∈ O(m), z ∈ O(k), i ∈ [n], j ∈ [m], (1.3.2a) (x • i y) • j+m-1 z = (x • j z) • i y, x ∈ O(n), y ∈ O(m), z ∈ O(k), i < j ∈ [n],
(1.3.2b)

1 • 1 x = x = x • i 1, x ∈ O(n), i ∈ [n]. (1.3.2c)
Since we consider in this paper only nonsymmetric operads, we shall call these simply operads. Moreover, in this work, we shall only consider operads O where O(1) has dimension 1.

If x is an element of O such that x ∈ O(n) for a n 1, we say that n is the arity of x and we denote it by |x|. An element

x of O of arity 2 is associative if x • 1 x = x • 2 x. If O 1 and O 2 are two operads, a linear map φ : O 1 → O 2 is an operad morphism if it respects arities,
H O (t) := n 1 dim O(n) t n .
(1.3.3) 1.3.2. Syntax trees and free operads. Let G := n 1 G(n) be a graded set. We say that the arity of an element x of G is n provided that x ∈ G(n). A syntax tree on G is a planar rooted tree such that its internal nodes of arity n are labeled on elements of arity n of G. The degree (resp. arity) of a syntax tree is its number of internal nodes (resp. leaves). For instance, if

G := G(2) G(3) with G(2) := {a, c} and G(3) := {b}, c a b b a (1.3.4)
is a syntax tree on G of degree 5 and arity 8. Its root is labeled by b and has arity 3.

The free operad over G is the operad Free(G) wherein for any n 1, Free(G)(n) is the linear span of the syntax trees on G of arity n, the partial composition s • i t of two syntax trees s and t on G consists in grafting the root of t on the ith leaf of s, and its unit is the tree consisting in one leaf. For instance, if

G := G(2) G(3) with G(2) := {a, c} and G(3) := {b}, one has in Free(G), a a b • 3 c a = a a c a b . (1.3.5)
We denote by c : G → Free(G) the inclusion map, sending any x of G to the corolla labeled by x, that is the syntax tree consisting in one internal node labeled by x attached to a required number of leaves. In the sequel, if required by the context, we shall implicitly see any element x of G as the corolla c(x) of Free(G). For instance, when x and y are two elements of G, we shall simply denote by x • i y the syntax tree c(x) • i c(y) for all valid integers i.

Presentations by generators and relations. A presentation of an operad

O consists in a pair (G, R) such that G := n 1 G(n) is a graded set, R is a subspace of Free(G), and O is isomorphic to Free(G)/ R ,
where R is the operad ideal of Free(G) generated by R. We call G the set of generators and R the space of relations of O. We say that O is quadratic if there is a presentation (G, R) of O such that R is a homogeneous subspace of Free(G) consisting in syntax trees of degree 2. Besides, we say that O is binary if there is a presentation (G, R) of O such that G is concentrated in arity 2. Furthermore, if O admits a presentation (G, R) and → is a rewrite rule on Free(G) such that the space induced by → is R , we say that → is an orientation of R.

1.3.4. Koszul duality and Koszulity. In [START_REF] Ginzburg | Koszul duality for operads[END_REF], Ginzburg and Kapranov extended the notion of Koszul duality of quadratic associative algebras to quadratic operads. Starting with a binary and quadratic operad O admitting a presentation (G, R) where G is finite, the Koszul dual of O is the operad O ! , isomorphic to the operad admitting the presentation (G, R ⊥ ) where R ⊥ is the annihilator of R in Free(G) with respect to the scalar product

-, -: Free(G)(3) ⊗ Free(G)(3) → K (1.3.6)
linearly defined, for all x, x , y, y ∈ G(2), by

x • i y, x • i y :=        1 if x = x , y = y , and i = i = 1, -1 if x = x , y = y , and i = i = 2, 0 otherwise. (1.3.7)
Then, with knowledge of a presentation of O, one can compute a presentation of O ! .

Besides, a quadratic operad O is Koszul if its Koszul complex is acyclic [GK94, LV12]. Furthermore, when O is Koszul and admits an Hilbert series, the Hilbert series of O and of its Koszul dual O ! are related [START_REF] Ginzburg | Koszul duality for operads[END_REF] by

H O (-H O ! (-t)) = t.
(1. 3.8) In this work, to prove the Koszulity of an operad O, we shall make use of a tool introduced by Dotsenko and Khoroshkin [DK10] in the context of Gröbner bases for operads, which reformulates in our context, by using rewrite rules on syntax trees, in the following way.

Lemma 1.3.1. Let O be an operad admitting a quadratic presentation (G, R). If there exists an orientation → of R such that → is a convergent rewrite rule, then O is Koszul.

When → satisfies the conditions contained in the statement of Lemma 1.3.1, the set of the normal forms of → forms a basis of O, called Poincaré-Birkhoff-Witt basis and arising in the work of Hoffbeck [START_REF] Hoffbeck | A Poincaré-Birkhoff-Witt criterion for Koszul operads[END_REF] (see also [START_REF] Loday | Algebraic Operads[END_REF]). 1.3.5. Algebras over an operad. Any operad O encodes a category of algebras whose objects are called O-algebras. An O-algebra A O is a vector space endowed with a left action

• : O(n) ⊗ A ⊗n O → A O , n 1, (1.3.9)
satisfying the relations imposed by the structure of O, that are

(x • i y) • (e 1 ⊗ • • • ⊗ e n+m-1 ) = x • (e 1 ⊗ • • • ⊗ e i-1 ⊗ y • (e i ⊗ • • • ⊗ e i+m-1 ) ⊗ e i+m ⊗ • • • ⊗ e n+m-1 ) , (1.3.10) for all x ∈ O(n), y ∈ O(m), i ∈ [n], and e 1 ⊗• • •⊗e n+m-1 ∈ A ⊗n+m-1 O . Notice that, by (1.3.10), if G is a generating set of O, it is enough to define the action of each x ∈ G on A ⊗|x| O
to wholly define •.

From posets to operads

This section is devoted to the introduction of our construction producing an operad from a poset. We also establish here some of its basic general properties. We end this section by presenting algebras over our operads and some of their properties.

2.1. Construction. Let us describe the construction As, associating with any poset a binary and quadratic operad presentation, and prove that it is functorial.

2.1.1. Operad presentations from posets. For any poset (Q, Q ), we define the Q-associative operad As(Q) as the operad admitting the presentation

(G Q , R Q ) where G Q is the set of generators G Q := G Q (2) := { a : a ∈ Q}, (2.1.1)
and R Q is the space of relations generated by

a • 1 b -a↑ Q b • 2 a↑ Q b , a, b ∈ Q and (a Q b or b Q a), (2.1.2a) a↑ Q b • 1 a↑ Q b -a • 2 b , a, b ∈ Q and (a Q b or b Q a). (2.1.2b)
By definition, As(Q) is a binary and quadratic operad.

Lemma 2.1.1. Let Q be a poset. For any a ∈ Q, let R a be the set

R a := { a • 1 b , b • 1 a , b • 2 a , a • 2 b : b ∈ Q and a Q b}. (2.1.3)
Then, for all x, y ∈ R a , x -y is an element of the space of relations R Q of As(Q).

Proof. This statement is a consequence of the definition of the space R Q through the elements (2.1.2a) and (2.1.2b). For instance, for x := a • 1 b and y := b • 1 a where b and b are elements of Q such that a Q b and a Q b , by (2.1.2a), we have that a

• 1 b -a • 2 a and b • 1 a -a • 2 a are in R Q . Thus, ( a • 1 b -a • 2 a ) -( b • 1 a -a • 2 a ) =
x -y also is. The proof for the other possibilities for x and y as elements of R a is analogous.

By Lemma 2.1.1, we observe that all a , a ∈ Q, are associative. For this reason, As(Q) is a generalization of the associative operad on several generating operations. As we will see in the sequel, this very simple way to produce operads has many combinatorial and algebraic properties.

2.1.2. Functoriality. For any morphism of posets φ : Q 1 → Q 2 , we denote by As(φ) the map

As(φ) : As(Q 1 )(2) → As(Q 2 )(2) (2.1.4) defined by As(φ) (π 1 ( x )) := π 2 φ(x) (2.1.5) for all x ∈ Q 1 , where π 1 : Free(G Q1 ) → As(Q 1 ) and π 2 : Free(G Q2 ) → As(Q 2 ) are canonical projections.
Lemma 2.1.2. Let Q 1 and Q 2 be two posets and φ : Q 1 → Q 2 be a morphism of posets. Then, the map As(φ) uniquely extends into an operad morphism from As(Q 1 ) to As(Q 2 ).

Proof. Let us denote by π 1 : Free(G Q1 ) → As(Q 1 ) and by π 2 : Free(G Q2 ) → As(Q 2 ) the canonical projections. Let r be an element of R Q1 of the form (2.1.2a). Then,

r = a • 1 b - a↑ Q 1 b • 2 a↑ Q 1 b
where a and b are two comparable elements of Q 1 . We have, by Lemma 1.1.1,

As(φ)(π 1 ( a ))• 1 As(φ)(π 1 ( b )) -As(φ)(π 1 ( a↑ Q 1 b )) • 2 As(φ)(π 1 ( a↑ Q 1 b )) = π 2 φ(a) • 1 π 2 ( φ(b) ) -π 2 φ(a↑ Q 1 b) • 2 π 2 φ(a↑ Q 1 b) = π 2 φ(a) • 1 π 2 φ(b) -π 2 φ(a)↑ Q 2 φ(b) • 2 π 2 φ(a)↑ Q 2 φ(b) = π 2 φ(a) • 1 φ(b) -φ(a)↑ Q 2 φ(b) • 2 φ(a)↑ Q 2 φ(b) = 0, (2.1.6)
showing that As(φ)(π 1 (r)) = 0. An analogous computation shows that the same property holds for all elements r of R Q1 of the form (2.1.2b). This shows that As(φ) extends in a unique way into an operad morphism.

Theorem 2.1.3. The construction As is a functor from the category of posets to the category of binary and quadratic operads.

Proof. By definition, the construction As sends any poset Q to an operad As(Q), defined by its presentation which is binary and quadratic. Moreover, by Lemma 2.1.2, As sends any morphism of posets φ to a morphism of operads As(φ). It follows the statement of the theorem. From the poset

Q := 1 2 3 4 , (2.1.7)
the operad As(Q) is binary and quadratic, generated by the set G Q = { 1 , 2 , 3 , 4 }, and, by Lemma 2.1.1, submitted to the relations

1 • 1 1 = 1 • 1 3 = 3 • 1 1 = 3 • 2 1 = 1 • 2 3 = 1 • 2 1 , (2.1.8a) 2 • 1 2 = 2 • 1 3 = 2 • 1 4 = 3 • 1 2 = 4 • 1 2 = 4 • 2 2 = 3 • 2 2 = 2 • 2 4 = 2 • 2 3 = 2 • 2 2 , (2.1.8b) 3 • 1 3 = 3 • 2 3 , (2.1.8c) 4 • 1 4 = 4 • 2 4 . (2.1.8d)
Besides, when Q is the trivial poset on the set [ ], 0, the operad As(Q) is generated by the set G Q = { 1 , . . . , } and, by Lemma 2.1.1, submitted to the relations

a • 1 a = a • 2 a , a ∈ [ ].
(2.1.9)

In particular, when = 0, As(Q) is the trivial operad, when = 1, As(Q) is the associative operad, and when = 2, As(Q) is the operad 2as [LR06]. These operads, for a generic 0, have been introduced in [Gir15b] under the name of dual multiassociative operads. These operads can be realized using Schröder trees [START_REF] Stanley | Enumerative Combinatorics[END_REF] with labelings satisfying some conditions. In Section 3.2.2, we shall describe a generalized version of this realization. Furthermore, when Q is the total order on the set [ ], 0, the operad As(Q) is generated by the set G Q = { 1 , . . . , } and, by Lemma 2.1.1, submitted to the relations

a • 1 a = a • 1 b = b • 1 a = b • 2 a = a • 2 b = a • 2 a , a b ∈ [ ].
(2.1.10)

In particular, when = 0, As(Q) is the trivial operad and when = 1, As(Q) is the associative operad. These operads, for a generic 0, have been introduced and studied in [Gir15b] under the name of multiassociative operads. They have the particularity to have stationary dimensions since dim As(Q)(1) = 1 and dim As(Q)(n) = for all n 2.

General properties.

Let us now list some general properties of the operad As(Q) where Q is a poset without particular requirements. We provide the dimension of the space of relations of As(Q), describe its associative elements, and give a necessary and sufficient condition for its basicity.

Space of relations dimensions.

Proposition 2.2.1. Let Q be a poset. Then, the dimension of the space R Q of relations of

As(Q) satisfies dim R Q = 4 int(Q) -3 #Q.
(2.2.1)

Proof. Consider the space R 1 generated by the elements of (2.1.2a) with a = b. Since these elements are linearly independent and are totally specified by two different elements a and b of Q such that a and b are comparable in Q, we have

dim R 1 = 2 (int(Q) -#Q) . (2.2.2)
For the same reason, the dimension of the space R 2 generated by the elements of (2.1.2b) with a = b satisfies dim R 2 = dim R 1 . The space R 3 generated by the elements of (2.1.2a) and (2.1.2b) with a = b consists in the space generated by a • 1 aa • 2 a , a ∈ Q, and is hence of dimension #Q. Therefore, since we have

R Q = R 1 ⊕ R 2 ⊕ R 3 , (2.2.3)
we obtain the stated formula (2.2.1) for dim R Q by summing the dimensions of R 1 , R 2 , and R 3 .

Associative elements.

Proposition 2.2.2. Let Q be a poset and Proof. Consider the element

C := {c 1 ≺ Q . . . ≺ Q c }
x := a∈Q λ a a (2.2.4)
of Free(G Q ), where λ a ∈ K for all a ∈ Q, such that π(x) is associative in As(Q). Then, since we have π(r) = 0 for all elements r of R Q , by Lemma 2.1.1, we have

π(x • 1 x -x • 2 x) = a,b∈Q λ a λ b π( a • 1 b -a • 2 b ) = a,b∈Q a Q b λ a λ b π( a • 1 b -a • 2 b ) + a,b∈Q b≺ Q a λ a λ b π( a • 1 b -a • 2 b ) + a,b∈Q a Q b b Q a λ a λ b π( a • 1 b -a • 2 b ) = a,b∈Q a Q b b Q a λ a λ b π( a • 1 b -a • 2 b ).
(2.2.5)

Now, the fact that π(x) is associative, that is π(x • 1 x -x • 2 x) = 0, is equivalent to the fact that the relations

λ a λ b = 0, a, b ∈ Q, a Q b,
• y i : O(n) → O(n + m -1), i ∈ [n],
(2.2.8) linearly defined by Proof. Assume that Q is not a trivial poset. Then, there are two elements a and b in Q such that a ≺ Q b. By denoting by π : Free(G Q ) → As(Q) the canonical projection, we have

• y i (x) := x • i y, x ∈ O(n), (2.2
• π( a ) 1 (π( a )) = π( a • 1 a ) (2.2.10) and • π( a ) 1 (π( b )) = π( b • 1 a ) = π( a • 1 a ). (2.2.11)
The second equality of (2.2.11) is a consequence of the fact that, by Lemma 2.1.1, the element

b • 1 a -a • 1 a belongs to the space R Q of relations of As(Q). Since a = b, π( a ) = π( b ), showing that the map • π( a ) 1
is not injective and thus, that As(Q) is not basic.

Conversely assume that Q is a trivial poset. The space R Q of relations As(Q) is hence generated by the a • 1 aa • 2 a , a ∈ Q. Therefore, for any syntax trees s and t of Free(G Q ), st is in R Q only if the roots of s and t have the same label. This implies that for all nonzero elements y of O, all the maps • y i are injective. Thus, As(Q) is basic.

Algebras over poset associative operads.

Let Q be a poset. From the presentation (G Q , R Q ) of the operad As(Q) provided by its definition in Section 2.1.1, an As(Q)-algebra is a vector space A endowed with linear operations

a : A ⊗ A → A, a ∈ Q, (2.3.1)
satisfying, for all x, y, z ∈ A, the relations

(x a y) b z = x a (y b z) = (x c y) a z = x c (y a z), a, b, c ∈ Q and a Q b and a Q c. (2.3.2) We call Q-associative algebra any As(Q)-algebra.
We shall exhibit two examples of Q-associative algebras in the sequel: in Section 3.2.3, free Q-associative algebras over one generator when Q is a forest poset and in Section 2.3.2, Q-associative algebras involving the antichains of the poset Q.

2.3.1. Units. Let Q be a poset and A be a Q-associative algebra. An a-unit, a ∈ Q, of A is an element 1 a of A satisfying

1 a a x = x = x a 1 a (2.3.3)
for all x ∈ A. Obviously, for any a ∈ Q there is at most one a-unit in A.

Besides, for any element x of A, we denote by E A (x) the set of elements a of Q such that x is an a-unit of A. Obviously, if 1 a is an a-unit of A, a ∈ E A (1 a ).

Proposition 2.3.1. Let Q be a poset and A be a Q-associative algebra. Then: (i) for any element x of A, E A (x) is an order filter of Q;

(ii) for all elements x and y of A such that x = y, the sets E A (x) and E A (y) are disjoint.

Proof. Assume that x is an element of A such that there is an element a of Q satisfying a ∈ E A (x). Then, by definition of E A (x), x is an a-unit of A. Thus, for all b of Q such that a Q b and all elements y of A, we have by (2.3.2),

x b y = (x a x) b y = (x a x) a y = x a y = y.
(2.3.4) By using similar arguments, we obtain that y b x = y, showing that x is a b-unit and hence, that b ∈ E A (x). This establishes (i).

Let us now consider two elements x and y of A such that there is an element a of Q satisfying a ∈ E A (x) ∩ E A (y). Then, by definition of E A (x) and E A (y), x and y are both a-units of A, implying that x = y. This implies (ii).

Proposition 2.3.1 implies that the sets E A (x), x ∈ A, form a partition of an order filter of Q where each part is itself an order filter of Q.

Antichains algebra.

Let Q be a poset and set X Q := {x a : a ∈ Q} as a set of commutative parameters and consider the commutative and associative polynomial algebra

K[X Q ]/ I Q , where I Q is the ideal of K[X Q ] generated by x a x b -x a , a Q b ∈ Q. (2.3.5)
Then, one observes that x a1 . . .

x a k is a reduced monomial of K[X Q ]/ I Q if and only if the set {a 1 , . . . , a k } is an antichain of Q of size k. We endow K[X Q ]/ I Q with linear operations a : K[X Q ]/ I Q ⊗ K[X Q ]/ I Q → K[X Q ]/ I Q , a ∈ Q, (2.3.6)
defined, for all reduced monomials x b1 . . .

x b k and x c1 . . . x c of K[X]/ I Q , by x b1 . . . x b k a x c1 . . . x c := π(x b1 . . . x b k x a x c1 . . . x c ), (2.3.7)
where π :

K[X Q ] → K[X Q ]/ I Q is the canonical projection. These operations a , a ∈ Q, endow K[X Q ]/ I Q with a structure of a Q-associative algebra.
Consider for instance the poset

Q := 1 2 3 4 5 .
(2.3.8)

The space K[X Q ]/ I Q is the linear span of the reduced monomials

x 1 , x 2 , x 3 , x 4 , x 5 , x 2 x 3 , x 2 x 4 , x 3 x 4 , x 3 x 5 , x 2 x 3 x 4 , (2.3.9) and one has for instance

x 2 3 x 4 = x 2 x 3 x 4 ,
(2.3.10a)

x 2 x 3 1 x 4 = x 1 , (2.3.10b) x 2 x 3 5 x 4 = x 2 x 3 x 4 .
(2.3.10c)

Forest posets, Koszul duality, and Koszulity

Here, we focus on the construction As when the input poset Q of the construction is a forest poset. In this case, we show that As(Q) is Koszul, provide a realization of As(Q), and obtain a functional equation for its Hilbert series. We end this section by computing presentations of the Koszul dual of As(Q).

Koszulity and Poincaré-Birkhoff-Witt bases.

We prove here that when Q is a forest poset, As(Q) is Koszul. For that, we consider an orientation of the space of relations R Q of As(Q) and show that this orientation is a convergent rewrite rule. This strategy to prove that As(Q) is Koszul is deduced, as explained in Section 1.3.4, from the works of Hoffbeck [START_REF] Hoffbeck | A Poincaré-Birkhoff-Witt criterion for Koszul operads[END_REF] and Dotsenko and Khoroshkin [DK10].

Orientation of the space of relations.

Let Q be a poset (not necessarily a forest poset just now) and → Q be the rewrite rule on Free(G Q ) satisfying

a • 1 b → Q a↑ Q b • 2 a↑ Q b , a, b ∈ Q and (a Q b or b Q a), (3.1.1a) a • 2 b → Q a↑ Q b • 2 a↑ Q b , a, b ∈ Q and (a ≺ Q b or b ≺ Q a). ( 3
-t ∈ R Q . It is enough to prove that s -t ∈ R Q implies s * ↔ Q t. Since R Q is generated by (2.1.2a) and (2.1.2b), we have two cases to consider. If s = a • 1 b and t = a↑ Q b • 2 a↑ Q b where a and b are two comparable elements of Q, by (3.1.1a), s → Q t. Otherwise, s = a↑ Q b • 1 a↑ Q b and t = a • 2 b where a and b are two comparable elements of Q. By setting r := a↑ Q b • 2 a↑ Q b , we have by (3.1.1a), s → Q r and, by (3.1.1b), t → Q r. Then, s * ↔ Q t.
Lemma 3.1.1 shows that the rewrite rule → Q is an orientation of the space of relations R Q of As(Q). Lemma 3.1.2. Let Q be a poset. Then, the rewrite rule → Q on Free(G Q ) is terminating.

Proof. Let n 1 and consider the map

φ : Free(G Q )(n) → N × Q n-1 (3.1.2)
such that for any syntax tree t of Free(G Q )(n), φ(t) := (α, u) where α is the sum, for all internal nodes x of t of the number of internal nodes in the right subtree of x, and u is the infix reading word of t. Let be the order relation on

N × Q n-1 satisfying (α, u) (α , u ) if α α and u i Q u i for all i ∈ [n -1].
For all comparable elements a and b of Q, we have

φ( a • 1 b ) = (0, ab) < (1, (a ↑ Q b) (a ↑ Q b)) = φ( a↑ Q b • 2 a↑ Q b ), (3.1.3)
and when in addition a = b,

φ( a • 2 b ) = (1, ab) < (1, (a ↑ Q b) (a ↑ Q b)) = φ( a↑ Q b • 2 a↑ Q b ). (3.1.4)
Therefore, for all syntax trees s and t such that s → Q t, φ(s) < φ(t). This implies that for all syntax trees s and t such that s = t and s * → Q t, φ(s) < φ(t). Now, since → Q preserves the arities of syntax trees and since the set Free(G Q )(n) is finite, → Q is terminating. Lemma 3.1.3. Let Q be a poset. Then, the set of normal forms of the rewrite rule → Q on Free(G Q ) is the set of the syntax trees t on Free(G Q ) such that for any internal node of t labeled by a having a left (resp. right) child labeled by b , a and b are incomparable (resp. are equal or are incomparable) in Q.

Proof. By Lemma 3.1.2, → Q is terminating. Therefore, → Q admits normal forms, which are by definition the syntax trees of Free(G Q ) that cannot be rewritten by → Q . These syntax trees are exactly the ones avoiding the patterns appearing as left members in (3.1.1a) and (3.1.1b), and are those described in the statement of the lemma.

Let us denote by N (Q) the set of normal forms of → Q , described in the statement of Lemma 3.1.3. Moreover, we denote by N (Q)(n), n 1, the set N (Q) restricted to syntax trees with exactly n leaves. From their description provided by Lemma 3.1.3, any tree t of N (Q) different from the leaf is of the recursive unique general form

t = s 1 s -1 s a a , (3.1.5)
where a ∈ Q and the dashed edge denotes a right comb tree wherein internal nodes are labeled by a and for any i ∈ [ ], s i is a tree of N (Q) such that s i is the leaf or its root is labeled by a b , b ∈ Q, so that a and b are incomparable in Q. (3.1.7e) Therefore, this shows that all critical pairs of → Q of trees consisting in three internal nodes or less are joinable. Since → Q is of degree 2 and is terminating (Lemma 3.1.2), by Lemma 1.2.1, this implies that → Q is confluent.

In Lemma 3.1.4, the condition on Q to be a forest poset is a necessary condition. Indeed, by setting

Q := 1 2 3 , ( 3
H Q (t) = t + a∈Q H a Q (t), (3.2.1)
where for all a ∈ Q, the

H a Q (t) satisfy H a Q (t) = t + Ha Q (t) t + Ha Q (t) + H a Q (t) , (3.2.2)
and for all a ∈ Q, the Ha

Q (t) satisfy Ha Q (t) = b∈Q a Q b b Q a H b Q (t). ( 3

.2.3)

Proof. By Theorem 3.1.5, As(Q) admits the set N (Q) as a Poincaré-Birkhoff-Witt basis, whose definition appears in the statement of Lemma 3.1.3. Then, by [START_REF] Hoffbeck | A Poincaré-Birkhoff-Witt criterion for Koszul operads[END_REF], for any n 1, the dimension of

As(Q)(n) is equal to the cardinality of N (Q)(n).
To enumerate the trees of N (Q), let us consider their description provided by Lemma 3.1.3 and their recursive general form provided by (3.1.5). In this manner, let t be a tree of N (Q) such that its root is labeled by a , a ∈ Q. Then, t has as a left subtree an element of N (Q) equal to the leaf or with a root labeled by b , b ∈ Q, such that a and b are incomparable in Q.

Moreover, t has as a right subtree an element of N (Q) equal to the leaf, or with a root labeled by c , c ∈ Q, such that a and c are incomparable in Q, or with a root labeled by a . This explains (3.2.2) since H a Q (t) is the generating series of the trees of N (Q) such that their roots are labeled by a , a ∈ Q, wherein Ha Q (t) is the series of trees of N (Q) such that their roots are labeled by b , b ∈ Q, where a and b are incomparable in Q. This also explains (3.2.3). Finally, since any tree of N (Q) is the leaf or has a root labeled by a a , a ∈ Q, the generating series of N (Q) satisfies (3.2.1).

For instance, let us use Proposition 3.2.1 for the operad As(Q) when Q is the total order on the set [ ],

0. This operad is the multiassociative operad [Gir15b], whose definition is recalled in Section 2.1.3. By (3.2.3), we have

Ha Q (t) = 0, a ∈ [ ], (3.2.4)
and hence, by (3.2.2),

H a Q (t) = t 2 1 -t , a ∈ [ ]. (3.2.5)
Then, by (3.2.1), the Hilbert series of As(Q) satisfies

H Q (t) = t + t 2 1 -t , 0. ( 3
(t) = H Q (t) -t -H a Q (t), a ∈ [ ]. ( 3
H a Q (t) = H Q (t) 2 1 + H Q (t) , a ∈ [ ].
(3.2.9) Therefore, by (3.2.1), the Hilbert series of As(Q) satisfies the quadratic functional equation

t + (t -1)H Q (t) + ( -1)H Q (t) 2 = 0, 0, (3.2.10)
and expresses as The first one is Sequence A006318, the second one is Sequence A103210, and the fourth one is Sequence A103211 and the last one is Sequence A133305 of [Slo].

H Q (t) = 1 -t -1 + (2 -4 )t + t 2 2( -1) , = 0 or 2. ( 3
Finally, let us use Proposition 3.2.1 for the operad As(Q) when Q is the forest poset

Q := 1 2 3 4 . ( 3
(t) = H2 Q (t) = H 3 Q (t) + H 4 Q (t), (3.2.17a) H3 Q (t) = H4 Q (t) = H 1 Q (t) + H 2 Q (t), (3.2.17b)
and, by (3.2.2) and straightforward computations, we obtain that

H 1 Q (t) = H 2 Q (t) = H 3 Q (t) = H 4 Q (t), (3.2.18)
so that the Hilbert series of As(Q) satisfies the quadratic functional equation

1 2 t + 1 4 t 2 + t - 1 2 H Q (t) + 3 4 H Q (t) 2 = 0. (3.2.19)
This Hilbert series expresses as 3.2.2. Realization. Let us describe a combinatorial realization of As(Q) when Q is a forest poset in terms of Schröder trees with a certain labeling and through an algorithm to compute their partial composition. Recall that a Schröder tree [START_REF] Stanley | Enumerative Combinatorics[END_REF] is a planar rooted tree wherein all internal nodes have two or more children.

H Q (t) = 1 -2t - √ 1 -10t + t 2 3 , ( 3
If Q is a poset (not necessarily a forest poset just now), a Q-Schröder tree is a Schröder tree where internal nodes are labeled on Q. For any element a of Q and any n 2, we denote by c n a the Q-Schröder tree consisting in a single internal node labeled by a attached to n leaves. We call these trees Q-corollas. A Q-alternating Schröder tree is a Q-Schröder tree t such that for any internal node y of t having a father x, the labels of x and y are incomparable in Q. We denote by S(Q) the set of Q-alternating Schröder trees and by S(Q)(n), n 1, the set S(Q) restricted to trees with exactly n leaves. Any tree t of S(Q) different from the leaf is of the recursive unique general form

t = s 1 s a . . . , (3.2.22)
where a ∈ Q and for any i ∈ [ ], s i is a tree of S(Q) such that s i is a leaf or its root is labeled by a b ∈ Q and a and b and incomparable in Q.

Relying on the description of the elements of N (Q) provided by Lemma 3.1.3 and on their recursive general form provided by (3.1.5), let us consider the map

s Q : N (Q)(n) → S(Q)(n), n 1, (3.2.23)
defined recursively by sending the leaf to the leaf and, for any tree t of N (Q) different from the leaf, by

s Q (t) = s Q       s 1 s -1 s a a       := s Q (s 1 ) s Q (s ) a . . . , (3.2.24)
where a ∈ Q and, in the syntax tree of (3.2.24), the dashed edge denotes a right comb tree wherein internal nodes are labeled by a and for any i ∈ [ ], s i is a tree of N (Q) such that s i is the leaf or its root is labeled by b , b ∈ Q, and a and b are incomparable in Q. It is immediate that s Q (t) is a Q-alternating Schröder tree, so that s Q is a well-defined map.

Lemma 3.2.2. Let Q be a poset. Then, for any n 1, the map s Q is a bijection between the set of syntax trees of N (Q)(n) with n leaves and the set S(Q)(n) of Q-alternating Schröder trees with n leaves.

Proof. The existence of the map s

-1 Q : S(Q)(n) → N (Q)(n), n
1, being the inverse of s Q , follows by structural induction on the trees of S(Q) and N (Q), relying on their respective recursive descriptions provided by (3.2.22) and (3.1.5). The statement of the lemma follows.

In order to define a partial composition for Q-alternating Schröder trees, we introduce the following rewrite rule. When Q is a forest poset, consider the rewrite rule Q on Q-Schröder trees (not necessarily Q-alternating Schröder trees) satisfying Lemma 3.2.3. Let Q be a poset. Then, the rewrite rule Q on Q-Schröder trees is terminating and the set of normal forms of Q is the set of Q-alternating Schröder trees. Moreover, when Q is a forest poset, Q is confluent.

Proof. Assume first that Q is only a poset. By definition of Q , if s and t are two Q-Schröder trees such that s Q t, t has less internal nodes than s. This implies that Q is terminating.

Since Q is terminating, its normal forms are by definition the Q-Schröder trees that cannot be rewritten by Q . These trees are exactly the ones avoiding the patterns appearing as left member in (3.2.25). Hence, if t is a normal form of Q and x and y are two internal nodes of t such that y is a child of x, the labels of x and y are incomparable in Q. Therefore, t is a Q-alternating Schröder tree.

Let us now prove that Q is confluent when Q is a forest poset. The Q-Schröder trees Moreover, all critical trees of Q consisting in three or less internal nodes are one of the two trees of (3.2.26).

During the rest of this proof, to gain clarity in our drawings of trees, we will represent labels of internal nodes by words a 1 . . . a k of elements of Q to specify the label a

1 ↑ Q . . . ↑ Q a k .
Because given a tree t of (3.2.26) there are exactly two ways to rewrite t in one step by Q , each critical tree of Q gives rise to one critical pair. By denoting by the relation Q , the fact that Q is a forest poset and Lemma 1.1.2 imply that we have the two graphs of rewriting by Q (3.2.27b) Therefore, this shows that all critical pairs of Q of trees consisting in three internal nodes of less are joinable. Since Q is of degree 2 and is terminating, by Lemma 1.2.1, this implies that Q is confluent.

In Lemma 3.2.3, the condition on Q to be a forest poset is a necessary condition for the confluence of Q . Indeed, by setting Since these two trees are normal forms of Q , this critical pair is not joinable and hence, Q is not confluent.

Q := 1 2 3 , ( 3
We define the partial composition s • i t of two Q-alternating Schröder trees s and t as the Q-alternating Schröder tree being the normal form by Q of the Q-Schröder tree obtained by grafting the root t on the ith leaf of s. We denote by ASchr(Q) the linear span of the set of the Q-alternating Schröder trees endowed with the partial composition described above and extended by linearity. Consider for instance the forest poset

Q := 1 2 3 4 5 6 . (3.2.31)
Then, we have in ASchr(Q) the partial composition

4 6 • 3 2 6 = 4 6 2 6 , (3.2.32)
and also

1 4 • 1 3 2 3 = 1 4 , (3.2.33)
since 3 2 3 1 4 Q 3 1 3 4 Q 3 1 4 Q 1 4 (3.2.34)
is a sequence of rewritings steps by → Q , where the leftmost tree of (3.2.34) is obtained by grafting the root of the second tree of (3.2.33) onto the first leaf of the first tree of (3.2.33).

Proposition 3.2.4. Let Q be a forest poset. Then, ASchr(Q) is an operad graded by the number of the leaves of the trees. Moreover, as an operad, ASchr(Q) is generated by the set of Q-corollas of arity two.

Proof. The fact that ASchr(Q) is an operad, that is it satisfies Relations (1.3.2a), (1.3.2b), and (1.3.2c), is a direct consequence of the fact that, by Lemma 3.2.3, the rewrite rule Q intervening in the computation of the partial compositions of two Q-alternating Schröder trees is convergent. This operad is graded by the number of the leaves of the trees by definition of its partial composition.

Finally, a straightforward structural induction on Q-alternating Schröder trees, relying on their recursive general form provided by (3.2.22), shows that any Q-alternating Schröder tree can be expressed by partial compositions involving only Q-corollas of arity two. Whence the second part of the statement of the proposition. Theorem 3.2.5. Let Q be a forest poset. Then, the operads As(Q) and ASchr(Q) are isomorphic.

Proof. First, by Proposition 3.2.4, ASchr(Q) is an operad wherein for any n 1, its graded component of arity n has bases indexed by Q-alternating Schröder trees with n leaves. By Lemma 3.2.2, these trees are in bijection with the elements of the Poincaré-Birkhoff-Witt basis N (Q) of As(Q) provided by Theorem 3.1.5. By [START_REF] Hoffbeck | A Poincaré-Birkhoff-Witt criterion for Koszul operads[END_REF], this shows that ASchr(Q) and As(Q) are isomorphic as graded vector spaces.

The generators of ASchr(Q), that are by Proposition 3.2.4 Q-corollas of arity two, satisfy at least the nontrivial relations

c 2 a • 1 c 2 b -c 2 a↑ Q b • 2 c 2 a↑ Q b = 0, a, b ∈ Q and (a Q b or b Q a), (3.2.35a) c 2 a↑ Q b • 1 c 2 a↑ Q b -c 2 a • 2 c 2 b = 0, a, b ∈ Q and (a Q b or b Q a), (3.2.35b)
obtained by a direct computation in ASchr(Q). By using the same reasoning as the one used to establish Proposition 2.2.1, we obtain that there are as many elements of the form ( Finally, by identifying all symbols c 2 a , a ∈ Q, with a , we observe that As(Q) and ASchr(Q) admit the same presentation. This implies that As(Q) and ASchr(Q) are isomorphic operads.

As announced, Theorem 3.2.5 provides a combinatorial realization ASchr(Q) of As(Q) when Q is a forest poset.

3.2.3.

Free forest poset associative algebras over one generator. The realization of As(Q), when Q is a forest poset, provided by Theorem 3.2.5 in terms of Q-alternating Schröder trees leads to the following description. The free Q-associative algebra over one generator, where Q is a forest poset, has ASchr(Q) as underlying vector space and is endowed with linear operations

a : ASchr(Q) ⊗ ASchr(Q) → ASchr(Q), a ∈ Q, (3.2.36)
satisfying for all Q-alternating Schröder trees s and t,

s a t = c 2 a • 2 t • 1 s. (3.2.37)
In an alternative way, s a t is the Q-alternating Schröder obtained by considering the normal form by Q of the tree obtained by grafting s and t respectively as left and right child of a binary corolla labeled by a.

Let us provide examples of computations in the free Q-associative algebra over one generator where Q is the forest poset (3.2.39e) 3.3. Koszul dual. We now establish a first presentation for the Koszul dual As(Q) ! of As(Q) where Q is a poset (and not necessarily a forest poset) and provide moreover a second presentation of As(Q) ! when Q is a forest poset. This second presentation of As(Q) ! is simpler than the first one and it shall be considered in the next section.

Q :=
G ¯ Q := G ¯ Q (2) := {¯ a : a ∈ Q}, (3.3.1)
and its space of relations R ¯ Q is generated by

¯ a • 1 ¯ a -¯ a • 2 ¯ a + b∈Q a≺ Q b (¯ b • 1 ¯ a + ¯ a • 1 ¯ b -¯ b • 2 ¯ a -¯ a • 2 ¯ b ), a ∈ Q, (3.3.2a) ¯ c • 1 ¯ d , c, d ∈ Q and c Q d and d Q c, (3.3.2b) ¯ c • 2 ¯ d , c, d ∈ Q and c Q d and d Q c. (3.3.2c) Proof. Let x := t∈Free(G Q )(3) λ t t, (3.3.3)
be an element of R Q , where the λ t are elements of K. By definition of the Koszul duality of operads, r, x = 0 for all r ∈ R Q , where -, -is the scalar product defined in (1.3.6). Then, Relations (2.1.2a) and (2.1.2b) imply the relations .3.4b) between the λ t , for all a, b ∈ Q such that a Q b or b Q a. This implies that x is of the form

λ a •1 b + λ a↑ Q b •2 a↑ Q b = 0, (3.3.4a) λ a↑ Q b •1 a↑ Q b + λ a •2 b = 0, ( 3
x = λ 1 a∈Q ( a • 1 a -a • 2 a ) + λ 1 a,b∈Q a≺ Q b ( b • 1 a + a • 1 b -b • 2 a -a • 2 b ) +λ 2 c,d∈Q c Q d d Q c ( c • 1 d ) + λ 3 c,d∈Q c Q d d Q c ( c • 2 d ), (3.3
(Q) ! satisfies dim R ¯ Q = 2 (#Q) 2 + 3 #Q -4 int(Q). (3.3.6)
Proof. To compute the dimension of the space of relations R ¯ Q of As(Q) ! , we consider the presentation of As(Q) ! exhibited by Proposition 3.3.1. Consider the space R 1 generated by the family consisting in the elements of (3.3.2a). Since this family is linearly independent and each of its elements is totally specified by an a of Q, R 1 is of dimension #Q. Consider now the space R 2 generated by the family consisting in the elements of (3.3.2b). This family is linearly independent and each of its elements is totally specified by two incomparable elements c and

d of Q. Since the number of pairs of comparable elements of Q is 2 int(Q) -#Q, we obtain dim R 2 = (#Q) 2 + #Q -2 int(Q).
(3.3.7)

For the same reason, the dimension of the space R 3 generated by the elements of (3.3.2c) satisfies dim R 3 = dim R 2 . Therefore, since

R ¯ Q = R 1 ⊕ R 2 ⊕ R 3 , (3.3.8)
we obtain the stated formula (3.3.6) by summing the dimensions of R 1 , R 2 , and R 3 .

Observe that, by Propositions 2.2.1 and 3.3.2, we have

dim R Q + dim R ¯ Q = 4 int(Q) -3 #Q + 2 (#Q) 2 + 3 #Q -4 int(Q) = 2 (#Q) 2 = dim Free(G Q )(3), ( 3
R ¯ Q is generated by ¯ a • 1 ¯ a -¯ a • 2 ¯ a , a ∈ Q, (3.3.13a)
¯ c • 1 ¯ d , c, d ∈ Q and c Q d and d Q c, (3.3.13b)
∈ Q, π ¯ a • 1 ¯ a -¯ a • 2 ¯ a = b,b ∈Q a Q b a Q b π (¯ b • 1 ¯ b ) -π (¯ b • 2 ¯ b ) = b∈Q a Q b π (¯ b • 1 ¯ b -¯ b • 2 ¯ b ) + b∈Q a Q b b ∈Q b≺ Q b π (¯ b • 1 ¯ b + ¯ b • 1 ¯ b -¯ b • 2 ¯ b -¯ b • 2 ¯ b ) = 0. ( 3
π ¯ c • 1 ¯ d = c ,d ∈Q c Q c d Q d π (¯ c • 1 ¯ d ) = 0. (3.3.15) Indeed, since Q is a forest poset, for all c , d ∈ Q such that c Q c and d Q d , c and d are incomparable in Q. We have shown that R ¯ Q is a subspace of R ¯ Q .
Finally, one can observe that all the elements (3.3.13a), (3.3.13b), and (3.3.13c) are linearly independent, and, by using the same arguments as the ones used in the proof of Proposition 3.3.2, we obtain dim

R ¯ Q = 2 (#Q) 2 + 3 #Q -4 int(Q). ( 3
G Q := G Q (2) := { a : a ∈ Q}, (3.3.17)
and the space of relations R Q is generated by The standard labeling of a thin forest poset Q consists in labeling the vertices of the Hasse diagram of Q from 1 to #Q in the order they appear in a depth first traversal, by always visiting in a same sibling the node with the biggest subtree as last. For instance, the standard labeling of a poset admitting In what follows, we shall consider only standardly labeled thin forest posets and we shall identify any element x of a thin forest posets Q as the label of x in the standard labeling of Q. Moreover, we shall see thin forest posets as forests of nonplanar rooted trees, obtained by considering Hasse diagrams of these posets.

a • 1 a -a • 2 a , a ∈ Q, (3.3.18a) a • 1 b , a, b ∈ Q and (a ≺ Q b or b ≺ Q a), (3.3.18b) a • 2 b , a, b ∈ Q and (a ≺ Q b or b ≺ Q a). ( 3
Q of As(Q) contains 1 • 1 1 = 1 • 1 2 = 2 • 1 1 = 1 • 1 3 = 3 • 1 1 = 3 • 2 1 = 1 • 2 3 = 2 • 2 1 = 1 • 2 2 = 1 • 2 1 , (3.3.20a) 2 • 1 2 = 2 • 2 2 , (3.3.20b) 3 • 1 3 = 3 • 2 3 . (3.3.20c) By Proposition 3.3.1, the space of relations R ¯ Q of As(Q) ! contains ¯ 1 • 1 ¯ 1 + ¯ 1 • 1 ¯ 2 + ¯ 2 • 1 ¯ 1 + ¯ 1 • 1 ¯ 3 + ¯ 3 • 1 ¯ 1 = ¯ 3 • 2 ¯ 1 + ¯ 1 • 2 ¯ 3 + ¯ 2 • 2 ¯ 1 + ¯ 1 • 2 ¯ 2 + ¯ 1 • 2 ¯ 1 , ( 3
Thin forest posets admit the following recursive description. If Q is a thin forest poset, then Q is the empty forest ∅, or it is the forest

Q (4.1.4)
consisting in the tree of one node (labeled by 1) and a thin forest poset Q , or it is the forest

Q (4.1.5)
consisting in one root (labeled by 1) attached to the roots of the trees of the thin forest poset Q . Therefore, there are 2 n-1 thin forest posets of size n 1.

Q := 1 2 3 4 5 6 . (4.1.6) Since 1 Q 2, 1 Q 3, 1 Q 4, 1 Q 5, 1 Q 6, 3 Q 4, 3 Q 5, 3 Q 6, 4 Q 5, 4 Q 6, in the dual Q ⊥ of Q we have 1 Q ⊥ 2, 1 Q ⊥ 3, 1 Q ⊥ 4, 1 Q ⊥ 5, 1 Q ⊥ 6, 3 Q ⊥ 4, 3 Q ⊥ 5, 3 Q ⊥ 6, 4 Q ⊥ 5, 4 Q ⊥ 6 and hence, Q ⊥ = 1 2 3 4 5 6 . (4.1.7)
Observe that this operation ⊥ is an involution on thin forest posets.

We now state two lemmas about thin forest posets and the operation ⊥ .

Lemma 4.1.1. Let Q be a thin forest poset. The dual Q ⊥ of Q admits the following recursive expression:

(i) if Q is the empty forest ∅, then ∅ ⊥ = ∅; (4.1.8) (ii) if Q is of the form Q = Q where Q is a thin forest poset, then ( Q ) ⊥ = Q ⊥ ; (4.1.9) (iii) otherwise, Q is of the form Q = Q
where Q is a thin forest poset, and then

Q ⊥ = Q ⊥ . (4.1.10)
Proof. We denote by ∨ the operation on thin forest posets defined in the statement of the lemma. To prove that ∨ = ⊥ , we proceed by structural induction on Q.

If Q = ∅, we have Q ⊥ = ∅ ⊥ = ∅ = ∅ ∨ = Q ∨ . Else, if Q is of the form Q = Q where Q is a thin forest poset, by definition of ⊥ , since 1 Q a implies a = 1, we have 1 Q ⊥ a for all a ∈ Q ⊥ . Now, by definition of ∨ , we have Q ∨ = ( Q ) ∨ = Q ∨ . (4.1.11)
Then, since 1 Q ∨ a for all a ∈ Q ∨ and, by induction hypothesis, Q ⊥ = Q ∨ , we obtain that

Q ⊥ = Q ∨ . Otherwise, Q is of the form Q = Q
where Q is a thin forest poset. By definition of ⊥, since 1 Q a for all a ∈ Q, we have 1 Q ⊥ a implies a = 1. Now, by definition of ∨, we have

Q ∨ = Q ∨ = Q ∨ . (4.1.12)
Then, since 1 Q ∨ a implies a = 1 and, by induction hypothesis, Q ⊥ = Q ∨ , we obtain that

Q ⊥ = Q ∨ .
Lemma 4.1.2. Let Q be a thin forest poset. Then, the number of intervals of Q and the number of intervals of its dual are related by

int(Q) + int Q ⊥ = (#Q) 2 + 3 #Q 2 . (4.1.13)
Proof. We proceed by structural induction on Q.

If Q = ∅, then Q ⊥ = Q and int(Q) + int Q ⊥ = 0, so that the statement of the lemma is satisfied. Else, if Q is of the form Q = Q where Q is a thin forest poset, by Lemma 4.1.1, ( Q ) ⊥ = Q ⊥ . (4.1.14) Now, we have int(Q) = int ( Q ) = 1 + int(Q ) (4.1.15) and int(Q ⊥ ) = int   Q ⊥   = 1 + int Q ⊥ + #Q ⊥ . ( 4
Q ⊥ = Q ⊥ = Q ⊥ , (4.1.17) so that int(Q) = int Q = 1 + int (Q ) + #Q (4.1.18) and int(Q ⊥ ) = int Q ⊥ = 1 + int Q ⊥ . (4.1.19)
By using the same arguments as those used for the previous case, the statement of the lemma is established. The dual poset of Q is

Q ⊥ = 1 2 3
dim R Q ⊥ = 4 int Q ⊥ -3 #Q = dim R ¯ Q . ( 4
= 2 (#Q) 2 + 3 #Q -4 int(Q) = 2 (#Q) 2 + 3 #Q -4 (#Q) 2 + 3 #Q 2 + 4 int Q ⊥ = 4 int Q ⊥ -3 #Q, (4.2.6)
establishing the second equality of (4.2.5) and implying the statement of the lemma.

Isomorphism.

Theorem 4.2.2. Let Q be a thin forest poset. Then, the map φ : As(Q ⊥ ) → As(Q) ! defined for any a ∈ Q ⊥ by φ( a ) := ¯ a extends in a unique way to an isomorphism of operads.

Proof. Let us denote by R ¯ Q the space of relations of As(Q) ! , expressed on the generating family G ¯ Q . This space is the same as the space R ¯ Q , described by Proposition 3.3.3. Let us exhibit a generating family of R ¯ Q as a vector space. For this, let π : Free(G ¯ Q ) → As(Q) ! be the canonical projection and let a and b be two elements of Q ⊥ such that a Q ⊥ b. We have, by using (4.2.1), We then have shown that the elements

π ¯ a • 1 ¯ b -¯ a • 2 ¯ a = a ,b ∈Q ⊥ a Q ⊥ a b Q ⊥ b π ¯ a • 1 ¯ b - a ,a ∈Q ⊥ a Q ⊥ a a Q ⊥ a π ¯ a • 2 ¯ a = a ∈Q ⊥ a Q ⊥ a π ¯ a • 1 ¯ a - a ∈Q ⊥ a Q ⊥ a π ¯ a • 2 ¯ a = 0.
¯ a • 1 ¯ b -¯ a↑ Q ⊥ b • 2 ¯ a↑ Q ⊥ b , a, b ∈ Q ⊥ and (a Q ⊥ b or b Q ⊥ a), (4.2.9a) ¯ a↑ Q ⊥ b • 1 ¯ a↑ Q ⊥ b -¯ a • 2 ¯ b , a, b ∈ Q ⊥ and (a Q ⊥ b or b Q ⊥ a). (4.2.9b) are in R ¯ Q .
It is immediate that the family consisting in the elements (4.2.9a) and (4.2.9b) is free. We denote by R the vector space generated by this family. By using the same arguments as the ones used in the proof of Proposition 2.2.1, we obtain that the dimension of R is Notice also that since the dual of the total order Q on a set of 0 elements is the trivial order Q ⊥ on the same set, by Theorem 4.2.2, As(Q) is the Koszul dual of As(Q ⊥ ). This is coherent with the results of [Gir15b] about the multiassociative operad (equal to As(Q)) and the dual multiassociative operad (equal to As(Q ⊥ )).

dim R = 4 int Q ⊥ -3 #Q ⊥ .

Conclusion and remaining questions

Through this work, we have presented a functorial construction As from posets to operads establishing a link between the two underlying categories. The operads obtained through this construction generalize the (dual) multiassociative operads introduced in [Gir15b]. As we have seen, some combinatorial properties of the starting posets Q imply properties on the obtained operads As(Q) as, among others, basicity and Koszulity. This work raises several questions. We have presented two classes of Q-associative algebras: the free Q-associative algebras over one generator where Q are forest posets and a polynomial algebra involving the antichains of a poset Q. The question to define free Q-associative algebras over one generator with no assumption on Q is open. Also, the question to define some other interesting Q-associative algebras has not been considered in this work and deserves to be addressed.

Besides, we have shown that when Q is a forest poset, As(Q) is Koszul. The property of being a forest poset for Q is only a sufficient condition for the Koszulity of As(Q) and the question to find a necessary condition is worthwhile. Notice that the strategy to prove the Koszulity of an operad by the partition poset method [MY91, Val07] (see also [START_REF] Loday | Algebraic Operads[END_REF]) cannot be applied to our context. Indeed, this strategy applies only on basic operads and we have shown that almost all operads As(Q) are not basic.

  Notations and general conventions. All the algebraic structures of this article have a field of characteristic zero K as ground field. For any integers a and c, [a, c] denotes the set {b ∈ N : a b c} and [n], the set [1, n]. The cardinality of a finite set S is denoted by #S. If u is a word, its letters are indexed from left to right from 1 to its length |u| and for any i ∈ [|u|], u i is the letter of u at position i. If is a generator of an operad O, we denote by ¯ the associated generator in the Koszul dual of O.

  and 4 Q 5. Moreover, Q avoids the pattern (1.1.5) since Q has no antichain of cardinality 3.

  For instance, let S be the set of all trees where internal nodes are labeled on {a, b, c} and consider the rewrite rule → on S satisfying b the following steps of rewritings by → :

  sends the unit of O 1 to the unit of O 2 , and commutes with partial composition maps. We say that O 2 is a suboperad of O 1 if O 2 is a graded subspace of O 1 , and O 1 and O 2 have the same unit and the same partial compositions. For any set G ⊆ O, the operad generated by G is the smallest suboperad of O containing G. When the operad generated by G is O itself and G is minimal with respect to inclusion among the subsets of O satisfying this property, G is a generating set of O and its elements are generators of O. An operad ideal of O is a graded subspace I of O such that, for any x ∈ O and y ∈ I, x • i y and y • j x are in I for all valid integers i and j. Given an operad ideal I of O, one can define the quotient operad O/ I of O by I in the usual way. When O is such that all O(n) are finite for all n 1, the Hilbert series of O is the series H O (t) defined by

2.1. 3 .

 3 First examples. Let us use Theorem 2.1.3 to exhibit some examples of constructions of binary an quadratic operads from posets.

  be a chain of Q. Then, the linear span C C of the set {π( c1 ), . . . , π( c )} contains only associative elements of As(Q), where π : Free(G Q ) → As(Q) is the canonical projection. Conversely, any associative element of As(Q) is an element of C C for a chain C of Q.

Lemma 3 .

 3 1.4. Let Q be a forest poset. Then, the rewrite rule → Q on Free(G Q ) is confluent.Proof. During this proof, to gain clarity in our drawings of trees, we will represent labels of internal nodes of syntax trees of Free(G Q ) only by their subscripts. For instance, an internal node labeled by a, a ∈ Q, denotes an internal node labeled by a . Moreover, a word a 1 . . . a k of elements of Q shall represent the element a 1 ↑ Q . . . ↑ Q a k . For instance, an internal node labeled by ab denotes an internal node labeled by a↑ Q b . Under these conventions, the syntax trees of → Q where in the first, third, and last trees, a and b are comparable and b and c are comparable, in the second tree, a and b are comparable and a and c are comparable, and in the fourth tree, a and c are comparable and b and c are comparable. Moreover, all critical trees of → Q consisting in three or less internal nodes are one of the five trees of (3.1.6).Because given a tree t of (3.1.6), there are exactly two ways to rewrite t in one step by → Q , each critical tree of → Q gives rise to one critical pair. By denoting by the reflexive closure of the relation → Q , the fact that Q is a forest poset and Lemma 1.1.2 imply that we have the five graphs of rewritings by → Q

  .2.20) and the dimensions of the first homogeneous components of As(Q) are 1, 4, 20, 124, 860, 6388, 49700, 399820, 3298700, 27759076. (3.2.21) Terms of this sequence are the ones of Sequence A107841 of [Slo] multiplied by 2.

  ∈ Q and (a Q b or b Q a). (3.2.25) Equation (3.2.34) shows examples of steps of rewritings by Q for the poset Q defined in (3.2.31).

  of Q where a and b are comparable in Q, and b and c are comparable in Q.

3. 3 . 1 .Proposition 3 . 3 . 1 .

 31331 Presentation by generators and relations. Let Q be a poset. Then, the Koszul dual As(Q) ! of As(Q) admits the following presentation. It is generated by

QProposition 3 . 3 . 3 .

 333 Alternative presentation. For any element a of a poset Q (not necessarily a forest poset just now), let ¯ a be the element of Free G ¯ Q (2) defined by¯ a := b∈Q a Q b ¯ b . (3.3.10) We denote by G ¯ Q the set of all ¯ a , a ∈ Q. By triangularity, the family G ¯ Q forms a basis of Free(G ¯ Q )(2)and hence, generates As(Q) ! . Consider for instance the poset then express as¯ 1 = ¯ 1 + ¯ 3 , (3.3.12a) ¯ 2 = ¯ 2 + ¯ 3 + ¯ 4 + ¯ 5 , (3.3.12b) ¯ 3 = ¯ 3 ,(3.3.12c)¯ 4 = ¯ 4 + ¯ 5 ,(3.3.12d) ¯ 5 = ¯ 5 . (3.3.12e) Let Q be a forest poset. Then, the operad As(Q) ! admits the following presentation. It is generated by G ¯ Q and its space of relations

¯ c • 2

 2 ¯ d , c, d ∈ Q and c Q d and d Q c. (3.3.13c) Proof. Let us show that R ¯ Q is equal to the space of relations R ¯ Q of As(Q) ! defined in the statement of Proposition 3.3.1. By this last proposition, for any x ∈ Free(G ¯ Q )(3), x is in R ¯ Q if and only if π(x) = 0 where π : Free(G ¯ Q ) → As(Q) ! is the canonical projection. Let us compute the image by π of the elements (3.3.13a), (3.3.13b), and (3.3.13c) generating R ¯ Q , by expanding these over the elements ¯ a , a ∈ Q, by using (3.3.10). We first have, for all a

  .3.14) Indeed, the second equality of (3.3.14) comes from the fact that π(¯ b • i ¯ b ) = 0 for all i = 1 or i = 2 whenever b and b are incomparable elements of Q. The last equality of (3.3.14) is a consequence of the fact that (3.3.2a) is in R ¯ Q . Moreover, for all incomparable elements c and d of Q, we have

  (4.1.1) as Hasse diagram produces the Hasse diagram

  .1.16) By induction hypothesis, we obtain that Q satisfies the statement of the lemma. Otherwise, Q is of the form Q = Q where Q is a thin forest poset. By Lemma 4.1.1,

4. 2 .Q

 2 Koszul duality and poset duality. By defining here an alternative basis for As(Q) when Q is a thin forest poset, we show that the construction As is closed under Koszul duality on thin forest posets. More precisely, we show that As(Q) ! and As(Q ⊥ ) are two isomorphic operads. 4.2.1. Alternative basis. Let Q be a thin forest poset. For any element b of Q, let ¯ b be the element of Free(G the set of all ¯ b , b ∈ Q. By triangularity, the family G ¯ Q forms a basis of Free(G ¯ Q )(2) and hence, generates As(Q) ! . Consider for instance the thin forest poset

  (4.2.7) Indeed the second equality of (4.2.7) comes, by Proposition 3.3.3, from the presence of the elements (3.3.13b) and (3.3.13c) in R ¯ Q , together with the fact that for all comparable elements a and b in Q, the fact that a Q ⊥ a, b Q ⊥ b, and a Q ⊥ b implies that a = b . Besides, the last equality of (4.2.7) comes, by Proposition 3.3.3, from the presence of the elements (3.3.13a) in R ¯ Q . Similar arguments show thatπ ¯ b • 1 ¯ a -¯ a • 2 ¯ a = 0, (4.2.8a) π ¯ a • 1 ¯ a -¯ b • 2 ¯ a = 0, (4.2.8b) π ¯ a • 1 ¯ a -¯ a • 2 ¯ b = 0. (4.2.8c)

  Lemma 4.2.1, we deduce that dim R = dim R ¯ Q = dim R ¯ Q , implying that R and R ¯ Q are equal.Therefore, the family of the G ¯ Q generating As(Q) ! is submitted to the same relations as the family of the G Q generating As(Q ⊥ ) (compare (4.2.9a) with (2.1.2a) and (4.2.9b) with (2.1.2b)). Whence the statement of the theorem.The isomorphism φ between As(Q ⊥ ) and As(Q) ! provided by Theorem 4.2.2 expresses from the generating familyG Q ⊥ of As(Q ⊥ ) to the generating family G ¯ Q of As(Q) ! , for any b ∈ Q ⊥ , as φ( b ) = a∈Q ⊥ a Q ⊥ b c∈Q a Q c ¯ c . (4.2.11)For instance, by considering the pair of thin forest posets in dualityQ, Q ⊥ =

  with the meaning that Properties of the poset Q Properties of the operad As(Q) Table

			Statement
	None	Binary and quadratic	Definition, Section 2.1.1
	Forest	Koszul	Theorem 3.1.5
	Thin forest	Closed under Koszul duality	Theorem 4.2.2
	Trivial	Basic	Proposition 2.2.3

  we say that t is rewritable by → into t and we denote this property by t * → t . In other words, * → is the reflexive and transitive closure of →. We denote by * ↔ the reflexive, transitive, and symmetric closure of →. The vector space induced by → is the subspace of the linear span of all trees of S generated by the family of all tt such that t

* ↔ t .

  Therefore, π(x) is an element of C C . Conversely, let x be an element of Free(G Q ) of the form (2.2.7) for a chain C of Q. Since the coefficients of x satisfy (2.2.6), by (2.2.5), π(x • 1 x -x • 2 x) = 0. Hence, x is associative.

		and b Q a	(2.2.6)
	are satisfied. This implies that x expresses as
	x =	λ c c ,	(2.2.7)
	c∈C
	where C is a chain of Q.

2.2.3. Basicity. An operad O is basic [Val07] if for any nonzero element y of O(m), m 1, all the maps

  Let Q be a poset. Then, the space induced by the rewrite rule→ Q on Free(G Q ) is the operad ideal of Free(G Q ) generated by the space of relations R Q of As(Q). Q , it is enough to prove that s → Q t implies s-t ∈ R Q .By a direct inspection of (3.1.1a) and (3.1.1b), we observe by Lemma 2.1.1 that st is in R Q . Conversely, let s and t be two syntax trees such that s

	.1.1b)
	3.1.2. Convergent rewrite rule.
	Lemma 3.1.1.

Proof. Let s and t be two syntax trees such that s * ↔ Q t. To prove that st ∈ R

  Let Q be a forest poset. Then, the operad As(Q) is Koszul and the set N (Q) of syntax trees of Free(G Q ) forms a Poincaré-Birkhoff-Witt basis of As(Q).

	of → Q admits the critical pair consisting in the two trees
	1	1
	1 ,	2	.	(3.1.10)
	2	2
	Since these two trees are normal forms of → Q , this critical pair is not joinable, hence showing
	that → Q is not confluent.
	3.1.3. Koszulity.
	Theorem 3.1.5.
				.1.8)
	the critical tree
	1
		3		(3.1.9)
	2

Proof. By Lemma 3.1.1, the rewrite rule → Q , defined by (3.1.1a) and

(3.1.1b)

, is an orientation of the space of relations R Q of As(Q). Moreover, by Lemmas 3.1.2 and 3.1.4, this rewrite rule is convergent when Q is a forest poset. Therefore, by Lemma 1.3.1, As(Q) is Koszul. Finally, by Lemma 3.1.3, N (Q) is the set of all normal forms of → Q and, by definition, forms a Poincaré-Birkhoff-Witt basis of As(Q).

3.2. Dimensions and realization.

The Koszulity, and more specifically the existence of a Poincaré-Birkhoff-Witt basis N (Q) highlighted by Theorem 3.1.5 for As(Q) when Q is a forest poset, lead to a combinatorial realization of As(Q). Before describing this realization, we shall provide a functional equation for the Hilbert series of As(Q). 3.2.1. Dimensions. Proposition 3.2.1. Let Q be a forest poset. Then, the Hilbert series H Q (t) of As(Q) satisfies

  3.2.35a) or (3.2.35b) as generating relations for the space of relations R Q of As(Q) (see (2.1.2a) and (2.1.2b)). Therefore, as ASchr(Q) and As(Q) are isomorphic as graded vector spaces, it cannot be more nontrivial relations in ASchr(Q) than Relations (3.2.35a) and (3.2.35b).

  .5) where λ 1 , λ 2 , and λ 3 are elements of K. Therefore, by identifying ¯ a with a for all a ∈ Q, we obtain that R ¯ Q is generated by the elements (3.3.2a), (3.3.2b), and (3.3.2c).

	Proposition 3.3.2. Let Q be a poset. Then, the dimension of the space R ¯ Q of relations of
	As

  ¯ Q and have the same dimension. The statement of the proposition follows. By considering the presentation of As(Q) ! furnished by Proposition 3.3.3 when Q is a forest poset, we obtain by Koszul duality a new presentation (G Q , R Q ) for As(Q) where the set of generators G Q is defined by

	.3.16)
	This shows that R

¯

Q and R

  As and by Lemma 2.1.1, the space of relations R

	Q :=	1	.	(3.3.19)
	2	3
	First, by definition of

.3.18c) 3.3.3. Example. To end this section, let us give a complete example of the spaces of relations R Q , R ¯ Q , R ¯ Q , and R Q of the operads As(Q) and As(Q) ! where Q is the forest poset

  .3.21a) 4.1.1. Description. A thin forest poset is a forest poset avoiding the pattern . In other words, a thin forest poset is a poset so that the nonplanar rooted tree t obtained by adding a (new) root to the Hasse diagram of Q has the following property. Any node x of t has at most one child y such that the bottom subtree of t rooted at y has two nodes or more.

	For instance,
	any forest poset admitting the Hasse diagram
	(4.1.1)
	is a thin forest poset while any forest poset admitting the Hasse diagram
	(4.1.2)
	is not.

  4.1.2. Duality. Given a thin forest posetQ, the dual of Q is the poset Q ⊥ such that, for all a, b ∈ Q ⊥ , a Q ⊥ b ifand only if a = b or a and b are incomparable in Q and a < b. For instance, consider the poset

  Let Q be a thin forest poset. Then, the dimension of the space R Q ⊥ of relations of As(Q ⊥ ) and the dimension of the space R ¯ Q of relations of As(Q) ! are related by

		(4.2.3)
	4
	5 6
	and hence, the elements of G Q express as ¯
	¯ 1 = ¯ 1 ,	(4.2.4a)
	¯ 2 = ¯ 1 + ¯ 2 ,	(4.2.4b)
	¯ 3 = ¯ 1 + ¯ 2 + ¯ 3 ,	(4.2.4c)
	¯ 4 = ¯ 1 + ¯ 2 + ¯ 4 ,	(4.2.4d)
	¯ 5 = ¯ 1 + ¯ 2 + ¯ 4 + ¯ 5 ,	(4.2.4e)
	¯ 6 = ¯ 1 + ¯ 2 + ¯ 4 + ¯ 6 .	(4.2.4f)
	Lemma 4.2.1.

  .2.5) Proof. First, by Proposition 2.2.1, the first equality of (4.2.5) is established. Moreover, by Proposition 3.3.2 and by Lemma 4.1.2, we have dim R ¯ Q

  (4.2.12) the map φ : As(Q ⊥ ) → As(Q) ! defined in the statement of Theorem 4.2.2 satisfiesφ( 1 ) = ¯ 1 , (4.2.13a) φ( 2 ) = ¯ 1 + ¯ 2 , (4.2.13b) φ( 3 ) = ¯ 1 + ¯ 2 + ¯ 3 + ¯ 4 + ¯ 5 + ¯ 6 , (4.2.13c) φ( 4 ) = ¯ 1 + ¯ 2 + ¯ 4 , (4.2.13d) φ( 5 ) = ¯ 1 + ¯ 2 + ¯ 4 + ¯ 5 + ¯ 6 , (4.2.13e) φ( 6 ) = ¯ 1 + ¯ 2 + ¯ 4 + ¯ 6 . As(Q ⊥ ) → As(Q) ! defined in the statement of Theorem 4.2.2 satisfies φ( 1 ) = ¯ 1 + ¯ 2 + ¯ 3 + ¯ 4 + ¯ 5 + ¯ 6 , (4.2.15a) φ( 2 ) = ¯ 2 + ¯ 3 + ¯ 4 + ¯ 5 + ¯ 6 ,

										(4.2.13f)
	Moreover, by considering the opposite pair of thin posets forests in duality
	Q, Q ⊥ =	   	3	1 2	4 5 6	,	1 2	3 4 5 6	    ,	(4.2.14)
	the map φ : (4.2.15b)
			φ( 3 ) = ¯ 3 ,				(4.2.15c)
	φ( 4 ) = ¯ 3 + ¯ 4 + ¯ 5 + ¯ 6 ,		(4.2.15d)
		φ( 5 ) = ¯ 3 + ¯ 5 ,			(4.2.15e)
	φ( 6 ) = ¯ 3 + ¯ 5 + ¯ 6 .			(4.2.15f)

Acknowledgements. The author warmly thanks the referees for their very careful reading and their suggestions, improving the quality of the paper.

Finally, by the observation established at the end of Section 3.3.2, the space of relations R Q of As(Q) contains

Thin forest posets and Koszul duality

As we have seen in Section 3, certain properties satisfied by the poset Q imply properties for the operad As(Q). In this section, we show that when Q is a forest poset with an extra condition, the Koszul dual As(Q) ! of As(Q) can be constructed via the construction As.

Thin forest posets.

A subclass of the class of forest posets, whose elements are called thin forest posets, is described here. We also define an involution on these posets linked, as we shall see later, to Koszul duality of the concerned operads.