PROPped up graph cohomology

M. Markl^{∗}^{1} and A.A. Voronov^{†}^{2}

1 Instutute of Mathematics, Academy of Sciences, Žitná 25, 115 67 Praha 1,

  The Czech Republic, markl@math.cas.cz

2 School of Mathematics, University of Minnesota, 206 Church St. S.E., Minneapolis, MN 55455, USA, voronov@math.umn.edu

Dedicated to Yuri I. Manin on the occasion of his seventieth birthday

Summary. We consider graph complexes with a flow and compute their cohomology. More specifically, we prove that for a PROP generated by a Koszul dioperad, the corresponding graph complex gives a minimal model of the PROP. We also give another proof of the existence of a minimal model of the bialgebra PROP from [14]. These results are based on the useful notion of a \frac{1}{2} PROP introduced by Kontsevich in [9].

Introduction

Graph cohomology is a term coined by M. Kontsevich [7, 8] for the cohomology of complexes spanned by graphs of a certain type with a differential given by vertex expansions (also known as splittings), i.e., all possible insertions of an edge in place of a vertex. Depending on the type of graphs considered, one gets various “classical” types of graph cohomology. One of them is the graph cohomology implicitly present in the work of M. Culler and K. Vogtmann [2]. It is isomorphic to the rational homology of the “outer space,” or equivalently, the rational homology of the outer automorphism group of a free group. Another type is the “fatgraph,” also known as “ribbon graph,” cohomology of R.C. Penner [17], which is isomorphic to the rational homology of the moduli spaces of algebraic curves.

These types of graph cohomology appear to be impossible to compute, at least at this ancient stage of development of mathematics. For example, the answer for ribbon graph cohomology is known only in a “stable” limit, as the genus goes to infinity, see a recent “hard” proof of the Mumford conjecture

∗Partially supported by the grant GA ČR 201/02/1390 and by the Academy of Sciences of the Czech Republic, Institutional Research Plan No. AV0Z10190503.

†Partially supported by NSF grant DMS-0227974.

by I. Madsen and M.S. Weiss [11]. No elementary method of computation seems to work: the graph complex becomes very complicated combinatorially in higher degrees. Even the apparently much simpler case of tree cohomology had been quite a tantalizing problem (except for the associative case, when the computation follows from the contractibility of the associahedra) until V. Ginzburg and M.M. Kapranov [6] attacked it by developing Koszul duality for operads.

This paper has originated from a project of computing the cohomology of a large class of graph complexes. The graph complexes under consideration are “PROPped up,” which means that the graphs are directed, provided with a flow, and decorated by the elements of a certain vector space associated to a given PROP. When this PROP is IB, the one describing infinitesimal bialgebras, see M. Aguiar [1], we get a directed version of the ribbon graph complex, while the PROP LieB describing Lie bialgebras gives a directed commutative version of the graph complex. In both cases, as well as in more general situations of a directed graph complex associated to a PROP coming from a Koszul dioperad in the sense of W.L. Gan [4] and of a similar graph complex with a differential perturbed in a certain way, we prove that the corresponding graph complex is acyclic in all degrees but one, see Corollary 28, answering a question of D. Sullivan in the Lie case. This answer stands in amazing contrast with anything one may expect from the nondirected counterparts of graph cohomology, such as the ones mentioned in the previous paragraphs: just putting a flow on graphs in a graph complex changes the situation so dramatically!

Another important goal of the paper is to construct free resolutions and minimal models of certain PROPs, which might be thought of as Koszul-like, thus generalizing both the papers of Ginzburg-Kapranov [6] and Gan [4], from trees (and operads and dioperads, respectively) to graphs (and PROPs). This is the content of Theorem 37 below. This theory is essential for understanding the notions of strongly homotopy structures described by the cobar construction for Koszul dioperads in [4] and the resolution of the bialgebra PROP in [14].

We also observe that axioms of some important algebraic structures over PROPs can be seen as perturbations of axioms of structures over \frac{1}{2} PROPs, objects in a way much smaller than PROPs and even smaller than dioperads, whose definition, suggested by Kontsevich [9], we give in Section 1.1. For example, we know from [14] that the PROP B describing bialgebras is a perturbation of the \frac{1}{2} PROP \frac{1}{2}b for \frac{1}{2}bialgebras (more precisely, B is a perturbation of the PROP generated by the \frac{1}{2} PROP \frac{1}{2}b). Another important perturbation of \frac{1}{2}b is the dioperad IB for infinitesimal bialgebras and, of course, also the PROP IB generated by this dioperad. In the same vein, the dioperad LieB describing Lie bialgebras and the corresponding PROP LieB are perturbations of the \frac{1}{2} PROP \frac{1}{2}lieb for \frac{1}{2}Lie bialgebras introduced in Example 20.

As we argued in [14], every minimal model of a PROP or dioperad which is a perturbation of a \frac{1}{2} PROP can be expected to be a perturbation of a minimal model of this \frac{1}{2} PROP. There however might be some unexpected technical difficulties in applying this principle, such as the convergence problem in the case of the bialgebra PROP, see Section 1.6.

The above observation can be employed to give a new proof of Gan’s results on Koszulness of the dioperads describing Lie bialgebras and infinitesimal bialgebras. First, one proves that the \frac{1}{2} PROPs \frac{1}{2}b and \frac{1}{2}lieb are Koszul in the sense of Section 1.4, simply repeating Gan’s proof in the simpler case of \frac{1}{2} PROPs. This means the \frac{1}{2} PROP cobar constructions on the quadratic duals of these \frac{1}{2} PROPs are minimal models thereof. Then one treats the dioperadic cobar constructions on the dioperadic quadratic duals of IB and LieB as perturbations of the dg dioperads freely generated by the \frac{1}{2} PROP cobar constructions and applies our perturbation theory to show that these dioperadic cobar constructions form minimal models of the corresponding dioperads, which is equivalent to their Koszulness.

This paper is based on ideas of the paper [14] by the first author and an e-mail message [9] from Kontsevich. The crucial notion of a \frac{1}{2} PROP (called in [9] a small PROP) and the idea that generating a PROP out of a \frac{1}{2} PROP constitutes a polynomial functor belong to him. Acknowledgment: We are grateful to Wee Liang Gan, Maxim Kontsevich, Sergei Merkulov, Jim Stasheff, and Dennis Sullivan for useful discussions.

Table of content: 1.1. PROPs, dioperads and \frac{1}{2} PROPs 1.2. Free PROPs 1.3. From \frac{1}{2} PROPs to PROPs 1.4. Quadratic duality and Koszulness for \frac{1}{2} PROPs 1.5. Perturbation techniques for graph cohomology 1.6. Minimal models of PROPs 1.7. Classical graph cohomology

1.1 PROPs, dioperads and \frac{1}{2}PROPs

Let k denote a ground field which will always be assumed of characteristic zero. This guarantees the complete reducibility of finite group representations. A PROP is a collection P = {P(m, n)}, m, n ≥ 1, of differential graded (dg) (Σ_{m}, Σ_{n})-bimodules (left Σ_{m}- right Σ_{n}-modules such that the left action commutes with the right one), together with two types of compositions, horizontal

⊗ : P(m_{1}, n_{1}) ⊗ ⋯ ⊗ P(m_{s}, n_{s}) → P(m_{1} + ⋯ + m_{s}, n_{1} + ⋯ + n_{s}),

defined for all m_{1}, …, m_{s}, n_{1}, …, n_{s} > 0, and vertical

∘ : P(m, n) ⊗ P(n, k) → P(m, k).

defined for all m, n, k > 0. These compositions respect the dg structures. One also assumes the existence of a unit 11 ∈ P(1, 1).

PROPs should satisfy axioms which could be read off from the example of the endomorphism PROP End_{V} of a vector space V, with End_{V} (m, n) the space of linear maps Hom(V^{⊗n}, V^{⊗m}) with n ‘inputs’ and m ‘outputs,’ 11 ∈ End_{V} (1, 1) the identity map, horizontal composition given by the tensor product of linear maps, and vertical composition by the ordinary composition of linear maps. For a precise definition see [10, 12].

Let us denote, for later use, by _{j}∘_{i} : P(m_{1}, n_{1}) ⊗ P(m_{2}, n_{2}) → P(m_{1} + m_{2} − 1, n_{1} + n_{2} − 1), a, b ↦ a _{j}∘_{i}b, 1 ≤ i ≤ n_{1}, 1 ≤ j ≤ m_{2}, the operation that composes the jth output of b to the ith input of a. Formally,

a _{j}∘_{i}b := (11 ⊗ ⋯ ⊗ 11 ⊗ a ⊗ 11 ⊗ ⋯ ⊗ 11)σ(11 ⊗ ⋯ ⊗ 11 ⊗ b ⊗ 11 ⊗ ⋯ ⊗ 11), (1.1)

where a is at the jth place, b is at the ith place and σ ∈ Σ_{n_{1}+m_{2}−1} is the block permutation ((12)(45))_{i−1,j−1,m_{2}−j,n_{1}−i}, see [4], where this operation was in fact denoted _{i}∘_{j}, for details.

It will also be convenient to introduce special notations for _{1}∘_{i} and _{j}∘_{1}, namely ∘_{i} := _{1}∘_{i} : P(m_{1}, n_{1}) ⊗ P(1, l) → P(m_{1}, n_{1} + l − 1), 1 ≤ i ≤ n_{1}, which can be defined simply by

a ∘_{i} b := a ∘ (11 ⊗ ⋯ ⊗ 11 ⊗ b ⊗ 11 ⊗ ⋯ ⊗ 11) (b at the i-th position), (1.2)

and, similarly, _{j}∘ := _{j}∘_{1}P(k, 1)⊗P(m_{2}, n_{2}) → P(m_{2} +k−1, n_{2}), 1 ≤ j ≤ m_{2}, which can be expressed as

c _{j}∘d := (11 ⊗ ⋯ ⊗ 11 ⊗ c ⊗ 11 ⊗ ⋯ ⊗ 11) ∘ d (c at the j-th position). (1.3)

A general iterated composition in a PROP is described by a ‘flow chart,’ which is a not necessarily connected graph of arbitrary genus, equipped with a ‘direction of gravity’ or a ‘flow,’ see Section 1.2 for more details. PROPs are in general gigantic objects, with P(m, n) infinite dimensional for any m and n. W.L. Gan [4] introduced dioperads which avoid this combinatorial explosion. Roughly speaking, a dioperad is a PROP in which only compositions along contractible graphs are allowed.

This can be formally expressed by saying that a dioperad is a collection D = {D(m, n)}, m, n ≥ 1, of dg (Σ_{m}, Σ_{n})-bimodules with compositions

j∘_{i} : D(m_{1}, n_{1}) ⊗ D(m_{2}, n_{2}) → D(m_{1} + m_{2} − 1, n_{1} + n_{2} − 1),

1 ≤ i ≤ n_{1}, 1 ≤ j ≤ m_{2}, that satisfy the axioms satisfied by operations _{j}∘_{i}, see (1.1), in a general PROP. Gan [4] observed that some interesting objects, like Lie bialgebras or infinitesimal bialgebras, can be defined using algebras over dioperads.

M. Kontsevich [9] suggested even more radical simplification consisting in considering objects for which only ∘_{i} and _{j}∘ compositions and their iterations are allowed. More precisely, he suggested:

Definition 1. A \frac{1}{2} PROP is a collection s = \{s(m, n)\} of dg (Σ_{m}, Σ_{n})- bimodules s(m, n) defined for all pairs of natural numbers except (m, n) = (1, 1), together with compositions

∘_{i} : s(m_{1}, n_{1}) ⊗ s(1, l) → s(m_{1}, n_{1} + l − 1), 1 ≤ i ≤ n_{1},  (1.4)

and

j∘ : s(k, 1) ⊗ s(m_{2}, n_{2}) → s(m_{2} + k − 1, n_{2}), 1 ≤ j ≤ m_{2},  (1.5)

that satisfy the axioms satisfied by operations ∘_{i} and _{j}∘, see (1.2), (1.3), in a general PROP.

We suggest as an exercise to unwrap the above definition, write the axioms explicitly, and compare them to the axioms of a dioperad in [4]. Observe that \frac{1}{2} PROPs cannot have units, because s(1, 1) is not there. Later we will also use the notation

∘ := ∘_{1} = _{1}∘ : s(k, 1) ⊗ s(1, l) → s(k, l), k, l ≥ 2.  (1.6)

The category of \frac{1}{2} PROPs will be denoted \frac{1}{2}PROP.

Example 2. Since \frac{1}{2} PROPs do not have units, their nature is close to that of pseudo-operads [15, Definition 1.16], which are, roughly, operads without units, with axioms defined in terms of ∘_{i}-operations. More precisely, the category of \frac{1}{2} PROPs s with s(m, n) = 0 for m ≥ 2, is isomorphic to the category of pseudo-operads P with P(0) = P(1) = 0. This isomorphism defines a faithful imbedding ι : Oper ↦ \frac{1}{2}PROP from the category Oper of pseudo-operads P with P(0) = P(1) = 0 to the category of \frac{1}{2} PROPs. To simplify the terminology, by ‘operad’ we will, in this paper, always understand a pseudo-operad in the above sense.

Example 3. Given a PROP P, there exists the ‘opposite’ PROP P^{†} with P^{†}(m, n) := P(n, m), for each m, n ≥ 1. A similar duality exists also for dioperads and \frac{1}{2} PROPs. Therefore one may define another faithful imbedding, ι^{†} : Oper ↦ \frac{1}{2}PROP, by ι^{†}(P) := ι(P)^{†}, where ι was defined in Example 2. The image of this imbedding consists of all \frac{1}{2} PROPs s with s(m, n) = 0 for all n ≥ 2.

Every PROP defines a dioperad by forgetting all compositions which are not allowed in a dioperad. In the same vein, each dioperad defines a \frac{1}{2} PROP if we forget all compositions not allowed in Definition 1. These observations can be organized into the following diagram of forgetful functors, in which diOp denotes the category of dioperads:

                     PROP ⟶^{1} diOp ⟶^{2} \frac{1}{2}PROP.  (1.7)

The left adjoints F_{1} : diOp → PROP and F_{2} : \frac{1}{2}PROP → diOp exist by general nonsense. In fact, we give, in Section 1.3, an explicit description of these functors. Of primary importance for us will be the composition

F := F_{1} ∘ F_{2} : \frac{1}{2}PROP → PROP,  (1.8)

which is clearly the left adjoint to the forgetful functor := _{2} ∘ _{1} : PROP → \frac{1}{2}PROP. Given a \frac{1}{2} PROP s, F (s) could be interpreted as the free PROP generated by the \frac{1}{2} PROP s.

Recall [10, 12] that an algebra over a PROP P is a morphism P → End_{V} of PROPs. The adjoints above offer an elegant way to introduce algebras over \frac{1}{2} PROPs and dioperads: an algebra over a \frac{1}{2} PROP s is simply an algebra over the PROP F (s) and, similarly, an algebra over a dioperad D is defined to be an algebra over the PROP F_{1}(D).

The following important theorem, whose proof we postpone to Section 1.3, follows from the fact, observed by M. Kontsevich in [9], that F and F_{2} are, in a certain sense, polynomial functors, see (1.10) and (1.11).

Theorem 4. The functors F : \frac{1}{2}PROP → PROP and F_{2} : \frac{1}{2}PROP → diOp are exact. This means that they commute with homology, that is, given a differential graded \frac{1}{2} PROP s, H_{∗}(F (s)) is naturally isomorphic to F (H_{∗}(s)). In particular, for any morphism α : s → t of dg \frac{1}{2} PROPs, the diagram of graded

PROPs

[figure: H_{∗}(F (s)); H_{∗}(F (t)); F (H_{∗}(s)); F (H_{∗}(s)); H_{∗}(F (α)); ≅; ≅; F (H_{∗}(α))]

is commutative. A similar statement is also true for F_{2} in place of F.

Let us emphasize here that we do not know whether functor F_{1} is exact or not. As a consequence of Theorem 4 we immediately obtain:

Corollary 5. A morphism α : s → t of dg \frac{1}{2} PROPs is a homology isomorphism if and only if F (α) : F (s) → F (t) is a homology isomorphism. A similar statement is also true for F_{2}.

Let us finish our catalogue of adjoint functors by the following definitions. By a bicollection we mean a sequence E = {E(m, n)}_{m,n≥1} of differential graded (Σ_{m}, Σ_{n})-bimodules such that E(1, 1) = 0. Let us denote by bCol the category of bicollections. Display (1.7) then can be completed into the following diagram of obvious forgetful functors:

                [figure: PROP; diOp; \frac{1}{2}PROP; bCol; 1; 2; P; \frac{1}{2} P; D]

Denote finally by Γ_{P} : bCol → PROP, Γ_{D} : bCol → diOp and Γ_{\frac{1}{2} P} : bCol → \frac{1}{2}PROP the left adjoints of the functors _{P}, _{D} and _{\frac{1}{2} P}, respectively.

Notation. We will use capital calligraphic letters P, Q, etc. to denote operads, small sans serif fonts s, t, etc. to denote \frac{1}{2} PROPs, capital italic fonts S, T, etc. to denote dioperads and capital sans serif fonts S, T, etc. to denote PROPs.

1.2 Free PROPs

To deal with free PROPs and resolutions, we need to fix a suitable notion of a graph. Thus, in this paper a graph or an (m, n)-graph, m, n ≥ 1, will mean a directed (i.e., each edge is equipped with direction) finite graph satisfying the following conditions:

1. the valence n(v) of each vertex v is at least three;

2. each vertex has at least one outgoing and at least one incoming edge;

3. there are no directed cycles;

4. there are precisely m outgoing and n incoming legs, by which we mean edges incident to a vertex on one side and having a “free end” on the other; these legs are called the outputs and the inputs, respectively;

5. the legs are labeled, the inputs by {1, …, n}, the outputs by {1, …, m}.

Note that graphs considered are not necessarily connected. Graphs with no vertices are also allowed. Those will be precisely the disjoint unions ↑↑ … ↑ of a number of directed edges. We will always assume the flow to go from bottom to top, when we sketch graphs.

Let v(G) denote the set of vertices of a graph G, e(G) the set of all edges, and Out(v) (respectively, In(v)) the set of outgoing (respectively, incoming) edges of a vertex v ∈ v(G). With an (m, n)-graph G, we will associate a geometric realization |G|, a CW complex whose 0-cells are the vertices of the graph G, as well as one extra 0-cell for each leg, and 1-cells are the edges of the graph. The 1-cells of |G| are attached to its 0-cells, as given by the graph. The genus gen(G) of a graph G is the first Betti number b_{1}(|G|) = rankH_{1}(|G|) of its geometric realization. This terminology derives from the theory of modular operads, but is not perfect, e.g., our genus is not what one usually means by the genus for ribbon graphs which are discussed in Section 1.7.

An isomorphism between two (m, n)-graphs G_{1} and G_{2} is a bijection between the vertices of G_{1} and G_{2} and a bijection between the edges thereof preserving the incidence relation, the edge directions and fixing each leg. Let Aut(G) denote the group of automorphisms of graph G. It is a finite group, being a subgroup of a finite permutation group.

Let E = {E(m, n) | m, n ≥ 1, (m, n) ≠ (1, 1)}, be a bicollection, see Section 1.1. A standard trick allows us to extend the bicollection E to pairs (A, B) of finite sets:

E(A, B) := Bij ([m], A) ×_{Σ_{m}} E(m, n) ×_{Σ_{n}} Bij (B, [n]),

where Bij denotes the set of bijections, [k] = {1, 2, …, k}, and A and B are any m- and n-element sets, respectively. We will mostly ignore such subtleties as distinguishing finite sets of the same cardinality in the sequel and hope this will cause no confusion. The inquisitive reader may look up an example of careful treatment of such things and what came out of it in [5].

For each graph G, define a vector space

E(G) := ⨂_{v∈v(G)} E(Out(v), In(v)).

Note that this is an unordered tensor product (in other words, a tensor product “ordered” by the elements of an index set), which makes a difference for the sign convention in graded algebra, see [15, page 64]. By definition, E(↑) = k. We will refer to an element of E(G) as a G-monomial. One may also think of a G-monomial as a decorated graph. Finally, let

Γ_{P}(E)(m, n) := ⨁_{G∈Gr(m,n)} E(G)_{Aut(G)}

be the (m, n)-space of the free PROP on E for m, n ≥ 1, where the summation runs over the set Gr(m, n) of isomorphism classes of all (m, n)-graphs G and

E(G)_{Aut(G)} := E(G)/Span(ge − e | g ∈ Aut(G), e ∈ E(G))

is the space of coinvariants of the natural action of the automorphism group Aut(G) of the graph G on the vector space E(G). The appearance of the automorphism group is due to the fact that the “right” definition would involve taking the colimit over the diagram of all graphs with respect to isomorphisms, see [5]. The space Γ_{P}(E)(m, n) is a (Σ_{m}, Σ_{n})-bimodule via the action by relabeling the legs. Moreover, the collection Γ_{P}(E) = {Γ_{P}(E)(m, n) | m, n ≥ 1} carries a natural PROP structure via disjoint union of decorated graphs as horizontal composition and grafting the outgoing legs of one decorated graph to the incoming legs of another one as vertical composition. The unit is given by 11 ∈ k = E(↑). The PROP Γ_{P}(E) is precisely the free PROP introduced at the end of Section 1.1.

1.3 From \frac{1}{2}PROPs to PROPs

Let us emphasize that in this article a dg free PROP means a dg PROP whose underlying (non-dg) PROP is freely generated (by a \frac{1}{2} PROP, dioperad, bicollection, ...) in the category of (non-dg) PROPs. Such PROPs are sometimes also called quasi-free or almost-free PROPs.

We are going to describe the structure of the functors F : \frac{1}{2}PROP → PROP and F_{2} : \frac{1}{2}PROP → diOp and prove that they commute with homology, i.e., prove Theorem 4. It is precisely the sense of Equations (1.9), (1.10), and (1.11) in which we say that the functors F and F_{2} are polynomial.

Let s be a dg \frac{1}{2} PROP. Then the dg free PROP F (s) generated by s may be described as follows. We call an (m, n)-graph G, see Section 1.2, reduced, if it has no internal edge which is either a unique output or unique input edge of a vertex. It is obvious that each graph can be modified to a reduced one by contracting all the edges violating this condition, i.e., the edges like this:

& ,

where a triangle denotes a graph with at least one vertex and exactly one leg in the direction pointed by the triangle, and a box denotes a graph with at least one vertex. For each reduced graph G, define a vector space

s(G) := ⨂_{v∈v(G)} s(Out(v), In(v)).  (1.9)

We claim that the PROP F (s) is given by

F (s)(m, n) = ⨁_{G∈\overline{Gr}(m,n)} s(G)_{Aut(G)},  (1.10)

where the summation runs over the set \overline{Gr}(m, n) of isomorphism classes of all reduced (m, n)-graphs G and s(G)_{Aut(G)} is the space of coinvariants of the natural action of the automorphism group Aut(G) of the graph G on the vector space s(G). The PROP structure on the whole collection {F (s)(m, n)} will be given by the action of the permutation groups by relabeling the legs and the horizontal and vertical compositions by disjoint union and grafting, respectively. If grafting creates a nonreduced graph, we will contract the bad edges and use suitable \frac{1}{2} PROP compositions to decorate the reduced graph appropriately.

A unit in the PROP F (s) is given by 11 ∈ s(↑). A differential is defined as follows. Define a differential on s(G) = ⨂_{v∈v(G)} s(Out(v), In(v)) as the standard differential on a tensor product of complexes. The action of Aut(G) on s(G) respects this differential and therefore the space s(G)_{Aut(G)} of coinvariants inherits a differential. Then we take the standard differential on the direct sum (1.10) of complexes.

Proposition 6. The dg PROP F (s) is the dg free PROP generated by a dg \frac{1}{2} PROP s, as defined in Section 1.1.

Proof. What we need to prove is that this construction delivers a left adjoint functor for the forgetful functor : PROP → \frac{1}{2}PROP. Let us define two maps

Mor_{\frac{1}{2}}_{PROP}(s, (P)) [figure: ψ; ϕ] Mor_{PROP}(F (s), P),

which will be inverses of each other. For a morphism f : s → (P) of \frac{1}{2} PROPs and a reduced graph decorated by elements s_{v} ∈ s(m, n) at each vertex v, we can always compose f(s_{v})’s in P as prescribed by the graph. The associativity of PROP compositions in P ensures the uniqueness of the result. This way we get a PROP morphism ϕ(f) : F (s) → P.

Given a PROP morphism g : F (s) → P, restrict it to the sub-\frac{1}{2} PROP s′ ⊂ F (s) given by decorated graphs with a unique vertex, such as . We define ψ(g) as the resulting morphism of \frac{1}{2} PROPs. ⊓ ⊔

Remark 7. The above construction of the dg free PROP F (s) generated by a \frac{1}{2} PROP s does not go through for the free PROP F_{1}(D) generated by a dioperad D. The reason is that there is no unique way to reduce an (m, n)- graph to a graph with all possible dioperadic compositions, i.e., all interior edges, contracted, as the following figure illustrates:

This suggests that the functor F_{1} may be not polynomial.

There is a similar description of the dg free dioperad F_{2}(s) generated by a dg \frac{1}{2} PROP s:

F_{2}(s)(m, n) = ⨁_{T ∈\overline{Tr}(m,n)} s(T).  (1.11)

Here the summation runs over the set \overline{Tr}(m, n) of isomorphism classes of all reduced contractible (m, n)-graphs T. The automorphism groups of these graphs are trivial and therefore do not show up in the formula. The following proposition is proven by an obvious modification of the proof of Proposition 6.

Proposition 8. The dg PROP F_{2}(s) is the dg free dioperad generated by a dg \frac{1}{2} PROP s, as defined in Section 1.1.

Proof of Theorem 4. Let us prove Theorem 4 for the dg free PROP F (s) generated by a dg \frac{1}{2} PROP s. The proof of the statement for F_{2}(s) will be analogous and even simpler, because of the absence of the automorphism groups of graphs.

Proposition 6 describes F (s) as a direct sum (1.10) of complexes s(G)_{Aut(G)}. Thus the homology H_{∗}(F (s)) is naturally isomorphic to

⨁_{G∈\overline{Gr}(m,n)} H_{∗}(s(G)_{Aut(G)}).

The automorphism group Aut(G) is finite, acts on s(G) respecting the differential, and, therefore, by Maschke’s theorem (remember, we work over a field of characteristic zero), the coinvariants commute naturally with homology:

H_{∗}(s(G)_{Aut(G)}) →^{∼} H_{∗}(s(G))_{Aut(G)}.

Then, using the Künneth formula, we get a natural isomorphism

H_{∗}(s(G)) →^{∼} ⨂_{v∈v(G)} H_{∗}(s(Out(v), In(v))).

Finally, combination of these isomorphisms results in a natural isomorphism

H_{∗}(F (s)) →^{∼} ⨁_{G∈\overline{Gr}(m,n)} ⨂_{v∈v(G)} H_{∗}(s(Out(v), In(v)))_{Aut(G)} = F (H_{∗}(s)).

The diagram in Theorem 4 is commutative, because of the naturality of the above isomorphisms. ⊓ ⊔

1.4 Quadratic duality and Koszulness for \frac{1}{2}PROPs

W.L. Gan defined in [4], for each dioperad D, a dg dioperad Ω_{D}(D) = (Ω_{D}(D), ∂), the cobar dual of D (DD in his notation). He also introduced quadratic dioperads, quadratic duality D ↦ D^{!}, and showed that, for each quadratic dioperad, there existed a natural map of dg dioperads α_{D} : Ω_{D}(D^{!}) → D. He called D Koszul, if α_{D} was a homology isomorphism. His theory is a dioperadic analog of a similar theory for operads developed in 1994 by V. Ginzburg and M.M. Kapranov [6]. The aim of this section is to build an analogous theory for \frac{1}{2} PROPs. Since the passage from \frac{1}{2} PROPs to PROPs is given by an exact functor, resolutions of \frac{1}{2} PROPs constructed with the help of this theory will induce resolutions in the category of PROPs.

Let us pause a little and recall, following [4], some facts about quadratic duality for dioperads in more detail. First, a quadratic dioperad is a dioperad D of the form

D = Γ_{D}(U, V)/(A, B, C),  (1.12)

where U = {U(m, n)} is a bicollection with U(m, n) = 0 for (m, n) ≠ (1, 2), V = {V (m, n)} is a bicollection with V (m, n) = 0 for (m, n) ≠ (2, 1), and (A, B, C) ⊂ Γ_{D}(U, V) denotes the dioperadic ideal generated by (Σ, Σ)-invariant subspaces A ⊂ Γ_{D}(U, V)(1, 3), B ⊂ Γ_{D}(U, V)(2, 2) and C ⊂ Γ_{D}(U, V)(3, 1). Notice that we use the original terminology of [6] where quadraticity refers to arities of generators and relations, rather than just relations. The dioperadic quadratic dual D^{!} is then defined as

D^{!} := Γ_{D}(U^{∨}, V^{∨})/(A^{⊥}, B^{⊥}, C^{⊥}),  (1.13)

where U^{∨} and V^{∨} are the linear duals with the action twisted by the sign representations (the Czech duals, see [15, p. 142]) and A^{⊥}, B^{⊥} and C^{⊥} are the annihilators of spaces A, B and C in

Γ_{D}(U^{∨}, V^{∨})(i, j) ≅ Γ_{D}(U, V)(i, j)^{∗},

where (i, j) = (1, 3), (2, 2) and (3, 1), respectively. See [4, Section 2] for details.

Quadratic \frac{1}{2} PROPs and their quadratic duals can then be defined in exactly the same way as sketched above for dioperads, only replacing everywhere Γ_{D} by Γ_{\frac{1}{2} P}. We say therefore that a \frac{1}{2} PROP s is quadratic if it is of the form

s = Γ_{\frac{1}{2} P}(U, V)/(A, B, C),

with U, V and (A, B, C) ⊂ Γ_{\frac{1}{2} P}(U, V) having a similar obvious meaning as for dioperads. The quadratic dual of s is defined by a formula completely analogous to (1.13):

s^{!} := Γ_{\frac{1}{2} P}(U^{∨}, V^{∨})/(A^{⊥}, B^{⊥}, C^{⊥}).

The apparent similarity of the above definitions however hides one very important subtlety. While

Γ_{D}(U^{∨}, V^{∨})(1, 3) ≅ Γ_{\frac{1}{2} P}(U^{∨}, V^{∨})(1, 3)

and

Γ_{D}(U^{∨}, V^{∨})(3, 1) ≅ Γ_{\frac{1}{2} P}(U^{∨}, V^{∨})(3, 1),

the (Σ_{2}, Σ_{2})-bimodules Γ_{D}(U^{∨}, V^{∨})(2, 2) and Γ_{\frac{1}{2} P}(U^{∨}, V^{∨})(2, 2) are substantially different, namely

Γ_{D}(U^{∨}, V^{∨})(2, 2) ≅ Γ_{\frac{1}{2} P}(U^{∨}, V^{∨})(2, 2) ⊕ Ind_{\{1\}}^{Σ_{2}×Σ_{2}}(U^{∨} ⊗ V^{∨}),

where Γ_{\frac{1}{2} P}(U^{∨}, V^{∨})(2, 2) ≅ V^{∨} ⊗ U^{∨}, see [4, section 2.4] for details.

We see that the annihilator of B ⊂ Γ_{\frac{1}{2} P}(E, F)(2, 2) in Γ_{\frac{1}{2} P}(E^{∨}, F^{∨})(2, 2) is much smaller than the annihilator of the same space taken in Γ_{D}(E^{∨}, F^{∨})(2, 2). A consequence of this observation is a rather stunning fact that quadratic duals do not commute with functor F_{2} : \frac{1}{2}PROP → diOp, that is, F_{2}(s^{!}) ≠ F_{2}(s)^{!}. The relation between s^{!} and F_{2}(s)^{!} is much finer and can be described as follows.

For a \frac{1}{2} PROP t, let ȷ(t) denote the dioperad which coincides with t as a bicollection and whose structure operations are those of t if they are allowed for \frac{1}{2} PROPs, and are trivial if they are not allowed for \frac{1}{2} PROPs. This clearly defines a functor ȷ : \frac{1}{2}PROP → diOp.

Lemma 9. Let s be a quadratic \frac{1}{2} PROP. Then F_{2}(s) is a quadratic dioperad and

F_{2}(s)^{!} ≅ ȷ(s^{!}).

Proof. The proof immediately follows from definitions and we may safely leave it to the reader. ⊓ ⊔

Remark 10. Obviously ȷ(s) = F_{2}(s^{!})^{!}. This means that the restriction of the functor ȷ : \frac{1}{2}PROP → diOp to the full subcategory of quadratic \frac{1}{2} PROPs can in fact be defined using quadratic duality.

The cobar dual Ω_{\frac{1}{2} P}(s) of a \frac{1}{2} PROP s and the canonical map α_{\frac{1}{2} P} : Ω_{\frac{1}{2} P}(s^{!}) → s can be defined by mimicking mechanically the analogous definitions for dioperads in [4], and we leave this task to the reader. The following lemma, whose proof is completely straightforward and hides no surprises, may in fact be interpreted as a characterization of these objects.

Lemma 11. For an arbitrary \frac{1}{2} PROP t, there exists a functorial isomorphism of dg dioperads

Ω_{D}(ȷ(t)) ≅ F_{2}(Ω_{\frac{1}{2} P}(t)).

If s is a quadratic \frac{1}{2} PROP, then the canonical maps

α_{\frac{1}{2} P} : Ω_{\frac{1}{2} P}(s^{!}) → s

and

α_{D} : Ω_{D}(F_{2}(s)^{!}) → F_{2}(s)

are related by

α_{D} = F_{2}(α_{\frac{1}{2} P}).  (1.14)

We say that a quadratic \frac{1}{2} PROP s is Koszul if the canonical map α_{\frac{1}{2} P} : Ω_{\frac{1}{2} P}(s^{!}) → s is a homology isomorphism. The following proposition is not unexpected, though it is in fact based on a rather deep Theorem 4.

Proposition 12. A quadratic \frac{1}{2} PROP s is Koszul if and only if F_{2}(s) is a Koszul dioperad.

Proof. The proposition immediately follows from (1.14) of Lemma 11 and Corollary 5 of Theorem 4. ⊓ ⊔

We close this section with a couple of important constructions and examples. Let P and Q be two operads. Recall from Examples 2 and 3 that P and Q can be considered as \frac{1}{2} PROPs, via imbeddings ι : Oper → \frac{1}{2}PROP and ι^{†} : Oper → \frac{1}{2}PROP, respectively. Let us denote

P ∗ Q^{†} := ι(P) ⊔ ι^{†}(Q)

the coproduct (“free product”) of \frac{1}{2} PROPs ι(P) and ι^{†}(Q). We will need also the quotient

P ⋄ Q^{†} := (ι(P) ⊔ ι^{†}(Q))/(ι^{†}(Q) ∘ ι(P)),

with (ι^{†}(Q) ∘ ι(P)) denoting the ideal generated by all q^{†} ∘ p, p ∈ ι(P) and q^{†} ∈ ι^{†}(Q); here ∘ is as in (1.6).

Exercise 13. Let P = Γ_{Op}(F)/(R) and Q = Γ_{Op}(G)/(S) be quadratic operads [15, Definition 3.31]; here Γ_{Op}(−) denotes the free operad functor. If we interpret F, G, R and S as bicollections with

F (1, 2) := F (2), G(2, 1) := G(2), R(1, 3) := R(3) and S(3, 1) := S(3), then we clearly have presentations (see (1.12))

P ∗ Q^{†} = Γ_{\frac{1}{2} P}(F, G)/(R, 0, S) and P ⋄ Q^{†} = Γ_{\frac{1}{2} P}(F, G)/(R, G ∘ F, S).

which show that both P ∗ Q^{†} and P ⋄ Q^{†} are quadratic \frac{1}{2} PROPs.

Exercise 14. Let Ass be the operad for associative algebras [15, Definition 1.12]. Verify that algebras over \frac{1}{2} PROP Ass ∗ Ass^{†} are given by a vector space V, an associative multiplication ^{•} : V ⊗ V → V and a coassociative comultiplication Δ : V → V ⊗V, with no relation between these two operations. Verify also that algebras over \frac{1}{2}b := Ass⋄Ass^{†} consists of an associative multiplication ^{•} and a coassociative comultiplication Δ as above, with the exchange rule

Δ(a^{•}b) = 0, for each a, b ∈ V.

These are exactly \frac{1}{2}bialgebras introduced in [14]. PROP F (\frac{1}{2}b) generated by \frac{1}{2} PROP \frac{1}{2}b is precisely PROP \frac{1}{2}B for \frac{1}{2}bialgebras considered in the same paper.

Exercise 15. Let P and Q be quadratic operads [15, Definition 3.31], with quadratic duals P^{!} and Q^{!}, respectively. Prove that the quadratic dual of the \frac{1}{2} PROP P ⋄ Q^{†} is given by

(P ⋄ Q^{†})^{!} = P^{!} ∗ (Q^{!})^{†}.

Example 16. The quadratic dual of \frac{1}{2} PROP \frac{1}{2}b introduced in Exercise 14 is Ass ∗ Ass^{†}. Let Lie denote the operad for Lie algebras [15, Definition 1.28] and Com the operad for commutative associative algebras [15, Definition 1.12]. The quadratic dual of \frac{1}{2} PROP \frac{1}{2}lieb := Lie ⋄ Lie^{†} is Com ∗ Com^{†}.

Gan defined a monoidal structure (E, F) ↦ E F on the category of bicollections such that dioperads were precisely monoids for this monoidal structure. Roughly speaking, E F was a sum over all directed contractible graphs G equipped with a level function ℓ : v(G) → {1, 2} such that vertices of level one (that is, vertices with ℓ(v) = 1) were decorated by E and vertices of level two were decorated by F. See [4, Section 4] for precise definitions. Needless to say, this should not be mistaken for the forgetful functors of Section 1.1.

Let D = Γ_{D}(U, V)/(A, B, C) be a quadratic dioperad as in (1.12), P := Γ_{0p}(U)/(A) and Q := Γ_{0p}(V)/(C). Let us interpret P as a bicollection with P(1, n) = P(n), n ≥ 1, and let Q^{op} be the bicollection with Q^{op}(n, 1) := Q(n), n ≥ 1, trivial for other values of (m, n). Since dioperads are -monoids in the category of bicollections, there are canonical maps of bicollections

φ : P Q^{op} → D and ϑ : Q^{op} P → D.

Let us formulate the following useful proposition.

Proposition 17. The canonical maps

φ : P Q^{op} → F_{2}(P ⋄ Q^{†}) and ϑ : (Q^{!})^{op} P^{!} → P^{!} ∗ (Q^{!})^{†}

are isomorphisms of bicollections.

Proof. The fact that φ is an isomorphism follows immediately from definitions. The second isomorphism can be obtained by quadratic duality: according to [4, Proposition 5.9(b)], F_{2}(P ⋄ Q^{†})^{!} ≅ (Q^{!})^{op} P^{!} while F_{2}(P ⋄ Q^{†})^{!} ≅ ȷ(P^{!} ∗ (Q^{!})^{†}) ≅ P^{!} ∗ (Q^{!})^{†} (isomorphisms of bicollections) by Lemma 9 and Exercise 15. ⊓ ⊔

The following theorem is again not surprising, because P ⋄ Q^{†} was constructed from operads P and Q using the relation

q^{†} ∘ p = 0, for p ∈ P and q ∈ Q^{†},

which is a rather trivial mixed distributive law in the sense of [3, Definition 11.1]. As such, it cannot create anything unexpected in the derived category; in particular, it cannot destroy the Koszulness of P and Q.

Theorem 18. If P and Q are Koszul quadratic operads, then P ⋄ Q^{†} is a Koszul \frac{1}{2} PROP. This implies that the bar construction Ω_{\frac{1}{2} P}(P^{!} ∗ (Q^{!})^{†}) is a minimal model, in the sense of Definition 30, of \frac{1}{2} PROP P ⋄ Q^{†}.

Proof. We will use the following result of Gan [4]. Given a quadratic dioperad D, suppose that the operads P and Q defined by P(n) := D(1, n) and Q := D(n, 1), n ≥ 2, are Koszul and that D ≅ P Q^{op}. Proposition 5.9(c) of [4] then states that D is a Koszul dioperad.

Since, by Proposition 17, F_{2}(P ⋄ Q^{†}) ≅ P Q^{op}, the above mentioned result implies that F_{2}(P ⋄ Q^{†}) is a Koszul quadratic dioperad. Theorem 18 now immediately follows from Proposition 12 and Exercise 15. ⊓ ⊔

Example 19. The following example is taken from [14], with signs altered to match the conventions of the present paper. The minimal model (see Definition 30) of \frac{1}{2} PROP \frac{1}{2}b for \frac{1}{2}bialgebras, given by the cobar dual Ω_{\frac{1}{2} P}(Ass ∗ Ass^{†}), equals

(Γ_{\frac{1}{2} P}(Ξ), ∂_{0}) ⟶^{α_{\frac{1}{2} P}} (\frac{1}{2}b, ∂ = 0),

where Ξ denotes the bicollection freely (Σ, Σ)-generated by the linear span Span({ξ_{n}^{m}}_{m,n∈I}) with

I := {m, n ≥ 1, (m, n) ≠ (1, 1)}.

The generator ξ_{n}^{m} of biarity (m, n) has degree n + m − 3. The map α_{\frac{1}{2} P} is defined by

α_{\frac{1}{2} P}(ξ_{2}^{1}) := , α_{\frac{1}{2} P}(ξ_{1}^{2}) := ,

while α_{\frac{1}{2} P} is trivial on all remaining generators. The differential ∂_{0} is given by the formula

∂_{0}(ξ_{n}^{m}) := (−1)^{m}ξ_{1}^{m} ∘ ξ_{n}^{1} + ∑_{U}(−1)^{i(s+1)+m+u−s}ξ_{u}^{m} ∘_{i} ξ_{s}^{1} (1.15)

+ ∑_{V}(−1)^{(v−j+1)(t+1)−1}ξ_{1}^{t} _{j}∘ξ_{n}^{v},

where we set ξ_{1}^{1} := 0,

U := {u, s ≥ 1, u + s = n + 1, 1 ≤ i ≤ u}

and

V = {t, v ≥ 1, t + v = m + 1, 1 ≤ j ≤ v}.

If we denote ξ_{2}^{1} = and ξ_{1}^{2} = , then ∂_{0}( ) = ∂_{0}( ) = 0. If ξ_{2}^{2} = , then

∂_{0}( ) = .

Under obvious, similar notation,

∂_{0}( ) = − ,
∂_{0}( ) = − + − + + ,
∂_{0}( ) = − + ,
∂_{0}( ) = − + ,
∂_{0}( ) = − − + ,
∂_{0}( ) = − + − − + ,
∂_{0}( ) = − − + − + , etc.

Example 20. In this example we discuss a minimal model of the \frac{1}{2} PROP \frac{1}{2}lieb introduced in Example 16. The \frac{1}{2} PROP \frac{1}{2}lieb describes \frac{1}{2}Lie bialgebras given by a vector space V with a Lie multiplication [−, −] : V ⊗ V → V and Lie comultiplication (diagonal) δ : V → V ⊗ V tied together by

δ[a, b] = 0 for all a, b ∈ V.

A minimal model of \frac{1}{2}lieb is given by the cobar dual Ω_{\frac{1}{2} P}(Com ∗ Com^{†}). It is clearly of the form

(Γ_{\frac{1}{2} P}(Υ), ∂_{0}) ⟶^{α_{\frac{1}{2} P}} (\frac{1}{2}lieb, ∂ = 0),

where Υ is the bicollection such that Υ (m, n) is the ground field placed in degree m + n − 3 with the sign representation of (Σ_{m}, Σ_{n}) for (m, n) ≠ 1, while Υ (1, 1) := 0. If we denote by 1_{n}^{m} the generator of Υ (m, n), then the map α_{\frac{1}{2} P} is defined by

α_{\frac{1}{2} P}(1_{2}^{1}) := , α_{\frac{1}{2} P}(1_{1}^{2}) := ,

while it is trivial on all remaining generators. There is a formula for the differential ∂_{0} which is in fact an anti-symmetric version of (1.15). We leave writing this formula, which contains a summation over unshuffles, as an exercise to the reader.

1.5 Perturbation techniques for graph cohomology

Let E be a bicollection. We are going to introduce, for an arbitrary fixed m and n, three very important gradings of the piece Γ_{P}(E)(m, n) of the free PROP Γ_{P}(E). We know, from Section 1.2, that Γ_{P}(E)(m, n) is the direct sum, over the graphs G ∈ Gr(m, n), of the vector spaces E(G)_{Aut(G)}. Recall that we refer to elements of E(G)_{Aut(G)} as G-monomials.

The first two gradings are of a purely topological nature. The component grading of a G-monomial f is defined by cmp(f) := cmp(G), where cmp(G) is the number of connected components of G minus one. The genus grading is given by the topological genus gen(G) of graphs (see Section 1.2 for a precise definition), that is, for a G-monomial f we put gen(f) := gen(G). Finally, there is another path grading, denoted pth(G), implicitly present in [9], defined as the total number of directed paths connecting inputs with outputs of G. It induces a grading of Γ_{P}(E)(m, n) by setting pth(f) := pth(G) for a Gmonomial f.

Exercise 21. Prove that for each G-monomial f ∈ Γ_{P}(E)(m, n),

gen(f) + max{m, n} ≤ pth(f) ≤ mn(gen(f) + 1)

and

cmp(f) ≤ min{m, n} − 1.

Find examples that show that these inequalities cannot be improved and observe that our assumption that E(m, n) is nonzero only for m, n ≥ 1, (m, n) ≠ (1, 1), is crucial.

Properties of these gradings are summarized in the following proposition.

Proposition 22. Suppose E is a bicollection of finite dimensional (Σ, Σ)- bimodules. Then, for any fixed d, the subspaces

Span{f ∈ Γ_{P}(E)(m, n); gen(f) = d}  (1.16)

and

Span{f ∈ Γ_{P}(E)(m, n); pth(f) = d},  (1.17)

where Span{−} is the k-linear span, are finite dimensional. The subspace Γ_{D}(E)(m, n) ⊂ Γ_{P}(E)(m, n) can be characterized as

[figure: •; •; •; p_{1}; p_{2}; w; v; u]

Fig. 1.1. Three branching points u, v and w of paths p_{1} and p_{2}.

Γ_{D}(E)(m, n) = Span{f ∈ Γ_{P}(E)(m, n); cmp(f) = gen(f) = 0}. (1.18)

For each f ∈ Γ_{D}(E)(m, n), pth(f) ≤ mn, and the subspace Γ_{\frac{1}{2} P}(E)(m, n) ⊂ Γ_{D}(E)(m, n) can be described as

Γ_{\frac{1}{2} P}(E)(m, n) = Span\{f ∈ Γ_{D}(E)(m, n); pth(f) = mn\}.  (1.19)

Proof. Since all vertices of our graphs are at least trivalent, it follows from standard combinatorics that there is only a finite number of (m, n)-graphs with a fixed genus. This proves the finite-dimensionality of the space in (1.16). Description (1.18) follows immediately from the definition of a dioperad. Our proof of the finite-dimensionality of the space in (1.17) is based on the following argument taken from [9].

Let us say that a vertex v is a branching vertex for a pair of directed paths p_{1}, p_{2} of a graph G ∈ Gr(m, n), if v is a vertex of both p_{1} and p_{2} and if it has the property that either there exist two different input edges f_{1}, f_{2} of v such that f_{s} ∈ p_{s}, s = 1, 2, or there exist two different output edges e_{1}, e_{2} of v such that e_{s} ∈ p_{s}, s = 1, 2. See also Figure 1.1. Denote br(p_{1}, p_{2}) the number of all branching vertices for p_{1} and p_{2}. A moment’s reflection convinces us that a pair of paths p_{1} and p_{2} with b branching points generates at least 2^{b−1} different paths in G, therefore 2^{br(p_{1},p_{2})−1} ≤ d, where d is the total number of directed paths in G. This implies that

br(p_{1}, p_{2}) ≤ log_{2}(d) + 1.

Now observe that each vertex is a branching point for at least one pair of paths. We conclude that the number of vertices of G must be less than or equal to d^{2} · (log_{2}(d) + 1).

The graph G cannot have vertices of valence bigger than d, because each vertex of valence k generates at least k − 1 different paths in G. Since there are only finitely many isomorphism classes of graphs with the number of

[figure: •; •; a; b; e; f; g; u; v; j_{1}; j_{2}; i_{1}; i_{2}]

Fig. 1.2. A configuration forbidden for \frac{1}{2} PROPs – f is a ‘bad’ edge. Vertices u and v might have more input or output edges which we did not indicate.

vertices bounded by a constant and with the valences of its vertices bounded by another constant, the finite-dimensionality of the space in (1.17) is proven.

Let us finally demonstrate (1.19). Observe first that for a graph G ∈ Gr(m, n) of genus 0, mn is actually an upper bound for pth(G), because for each output-input pair (i, j) there exists at most one path joining i with j (genus 0 assumption). It is also not difficult to see that pth(f) = mn for a G-monomial f ∈ Γ_{\frac{1}{2} P}(E). So it remains to prove that pth(f) = mn implies f ∈ Γ_{\frac{1}{2} P}(E).

Suppose that f is a G-monomial such that f ∈ Γ_{D}(E)(m, n)\Γ_{\frac{1}{2} P}(E)(m, n). This happens exactly when G contains a configuration shown in Figure 1.2, forbidden for \frac{1}{2} PROPs. Then there certainly exists a path p_{1} containing edges e and a, and another path p_{2} containing edges b and g. Suppose that p_{s} connects output i_{s} with input j_{s}, i = 1, 2, as in Figure 1.2. It is then clear that there is no path that connects i_{2} with j_{1}, which means that the total number of paths in G is not maximal. This finishes the proof of the proposition. ⊓ ⊔

Remark 23. As we already know, there are various ‘restricted’ versions of PROPs characterized by types of graphs along which the composition is allowed. Thus \frac{1}{2} PROPs live on contractible graphs without ‘bad’ edges as in Figure 1.2, and Gan’s dioperads live on all contractible graphs. A version of PROPs for which only compositions along connected graphs are allowed was studied by Vallette who called these PROPs properads [19]. All this can be summarized by a chain of inclusions of full subcategories

               Oper ⊂ \frac{1}{2}PROP ⊂ diOp ⊂ Proper ⊂ PROP.

Let Γ_{pth}(E) ⊂ Γ_{P}(E) be the subspace spanned by all G-monomials such that G is contractible and contains at least one ‘bad’ edge as in Figure 1.2.

By Proposition 22, one might equivalently define Γ_{pth}(E) by

Γ_{pth}(E)(m, n) =

= Span{f ∈ Γ_{D}(E)(m, n); cmp(f) = gen(f) = 0, and pth(f) < mn}.

If we denote

Γ_{c+g}(E) := Span{f ∈ Γ_{P}(E); cmp(f) + gen(f) > 0}

then there is a natural decomposition

Γ_{P}(E) = Γ_{\frac{1}{2} P}(E) ⊕ Γ_{pth}(E) ⊕ Γ_{c+g}(E)

in which clearly Γ_{\frac{1}{2} P}(E)⊕Γ_{pth}(E) = Γ_{D}(E). Let π_{\frac{1}{2} P}, π_{pth} and π_{c+g} denote the corresponding projections. For a degree −1 differential ∂ on Γ_{P}(E), introduce derivations ∂_{0}, ∂_{pth} and ∂_{c+g} determined by their restrictions to the generators E as follows:

∂_{0}|_{E} := π_{\frac{1}{2} P} ∘ ∂|_{E}, ∂_{pth}|_{E} := π_{pth} ∘ ∂|_{E} and ∂_{c+g}|_{E} := π_{c+g} ∘ ∂|_{E}.

Let us define also ∂_{D} := ∂_{0}+∂_{pth}, the dioperadic part of ∂. The decompositions

∂ = ∂_{D} + ∂_{c+g} = ∂_{0} + ∂_{pth} + ∂_{c+g}  (1.20)

are fundamental for our purposes. We will call them the canonical decompositions of the differential ∂. The following example shows that, in general, ∂_{0}, ∂_{D} and ∂_{c+g} need not be differentials, as they may not square to zero.

Example 24. Let us consider the free PROP Γ_{P}(a, b, c, u, x), where the generator a has degree 1 and biarity (4, 2), b degree 0 and biarity (2, 1), c degree 1 and biarity (4, 1), u degree 0 and biarity (2, 1), and x degree 2 and biarity (4, 1). Define a degree −1 differential ∂ by the following formulas whose meaning is, as we believe, clear:

∂ ( x) :=  \begin{matrix}a \\ b \end{matrix} + c, ∂ ( a) := u ⊗ u, ∂ ( c) := −  b u  u,

while ∂(b) = ∂(u) = 0. One can easily verify that ∂^{2} = 0. By definition,

∂_{0} ( x) = c , ∂_{0} ( a) = 0, ∂_{0} ( c) = −  b u  u

and, of course, ∂_{0}(b) = ∂_{0}(u) = 0. A simple calculation shows that

∂_{0}^{2} ( x) = −  b u  u

therefore ∂_{0}^{2} ≠ 0. Since ∂_{0} = ∂_{D}, we conclude that also ∂_{D}^{2} ≠ 0.

Let us formulate some conditions which guarantee that the derivations ∂_{0} and ∂_{D} square to zero. We say that a differential ∂ in Γ_{P}(E) is connected if cmp(∂(e)) = 0 for each e ∈ E. Similarly we say that ∂ has genus zero if gen(∂(e)) = 0 for e ∈ E. Less formally, connectivity of ∂ means that ∂(e) is a sum of G-monomials with all G’s connected, and ∂ has genus zero if ∂(e) is a sum of G-monomials with all G’s of genus 0 (but not necessarily connected).

Proposition 25. In the canonical decomposition (1.20) of a differential ∂ in a free PROP Γ_{P}(E), ∂_{D}^{2} = 0 always implies that ∂_{0}^{2} = 0.

If moreover either (i) the differential ∂ is connected or (ii) ∂ has genus zero, then ∂_{D}^{2} = 0, therefore both ∂_{0} and ∂_{D} are differentials on Γ_{P}(E).

Proof. For a G-monomial f, write

∂_{D}(f) = ∑_{H∈U} g_{H},  (1.21)

the sum of H-monomials g_{H} over a finite set U of graphs. Since ∂_{D} is a derivation, each H ∈ U is obtained by replacing a vertex v ∈ v(G) of biarity (s, t) by a graph R of the same biarity. It follows from the definition of the dioperadic part ∂_{D} that each such R is contractible. This implies that all graphs H ∈ U which nontrivially contribute to the sum (1.21) have the property that pth(H) ≤ pth(G) (∂_{D} does not increase the path grading) and that

∂_{0}(f) = ∑_{H∈U_{0}} g_{H}, where U_{0} := {H ∈ U; pth(H) = pth(G)}.  (1.22)

This can be seen as follows. It is clear that a replacement of a vertex by a contractible graph cannot increase the total number of paths in G. This implies that ∂_{D} does not increase the path grading. Equation (1.22) follows from the observation that decreasing the path grading locally at a vertex decreases the path grading of the whole graph. By this we mean the following.

Assume that a vertex v of biarity (s, t) is replaced by a contractible graph R such that pth(R) < st. This means that there exists an output-input pair (i, j) of R for which there is no path in R connecting output i with input j. On the other hand, in G there certainly existed a path that ran through output i and input j of vertex v and broke apart when we replaced v by R.

Now we see that ∂_{0}^{2} is precisely the part of ∂_{D}^{2} which preserves the path grading. This makes the implication (∂_{D}^{2} = 0) ⟹ (∂_{0}^{2} = 0) completely obvious and proves the first part of the proposition.

For the proof of the second half, it will be convenient to introduce still another grading by putting

grad(G) := cmp(G) − gen(G) = +|v(G)| − |e(G)| − 1,  (1.23)

where |v(G)| denotes the number of vertices and |e(G)| the number of internal edges of G. Let f be a G-monomial as above. Let us consider a sum similar to (1.21), but this time for the entire differential ∂:

∂(f) = ∑_{H∈S} g_{H},

where S is a finite set of graphs. We claim that, under assumptions (i) or (ii),

∂_{D}(f) = ∑_{H∈S_{D}} g_{H}, where S_{D} := {H ∈ S; grad(H) = grad(G)}.  (1.24)

This would clearly imply that ∂_{D}^{2} is exactly the part of ∂^{2} that preserves the grad-grading, therefore ∂_{D}^{2} = 0.

As in the first half of the proof, each H ∈ S is obtained from G by replacing v ∈ v(G) by some graph R. In case (i), R is connected, that is cmp(G) = cmp(H) for all H ∈ S. It follows from an elementary algebraic topology that gen(H) ≥ gen(G) and that gen(G) = gen(H) if and only if gen(R) = 0. This proves (1.24) for connected differentials.

Assume now that ∂ has genus zero, that is, gen(R) = 0. This means that R can be contracted to a disjoint R′ union of cmp(R)+1 corollas. Since grad(−) is a topological invariant, we may replace R inside H by its contraction R′. We obtain a graph H′ for which grad(H) = grad(H′). It is obvious that H′ has the same number of internal edges as G and that |v(H′)| = |v(G)| + cmp(R), therefore grad(G) = grad(H) + cmp(R). This means that grad(G) = grad(H) if and only if cmp(R) = 0, i.e. if R is connected. This proves (1.24) in case (ii) and finishes the proof of the Proposition. ⊓ ⊔

The following theorem will be our basic tool to calculate the homology of free differential graded PROPs in terms of the canonical decomposition of the differential.

Theorem 26. Let (Γ_{P}(E), ∂) be a dg free PROP and m, n fixed natural numbers.

(i) Suppose that the differential ∂ is connected. Then the genus grading defines, by

F_{p}^{gen} := Span{f ∈ Γ_{P}(E)(m, n); gen(f) ≥ −p},  (1.25)

an increasing ∂-invariant filtration of Γ_{P}(E)(m, n).

(ii) If the differential ∂ has genus zero, then

F_{p}^{grad} := Span{f ∈ Γ_{P}(E)(m, n); grad(f) ≥ −p}.

is also an increasing ∂-invariant filtration of Γ_{P}(E)(m, n).

The spectral sequences induced by these filtrations have both the first term isomorphic to (Γ_{P}(E)(m, n), ∂_{D}) and they both abut to H_{∗}(Γ_{P}(E)(m, n), ∂).

(iii) Suppose that ∂_{D}^{2} = 0. Then the path grading defines an increasing ∂_{D}-invariant filtration

F_{p}^{pth} := Span{f ∈ Γ_{P}(E)(m, n); pth(f) ≤ p}.

This filtration induces a first quadrant spectral sequence whose first term is isomorphic to (Γ_{P}(E)(m, n), ∂_{0}) and which converges to H_{∗}(Γ_{P}(E)(m, n), ∂_{D}).

Proof. The proof easily follows from Proposition 25 and the analysis of the canonical decomposition given in the proof of that proposition. ⊓ ⊔

The following proposition describes an important particular case when the spectral sequence induced by the filtration (1.25) converges.

Proposition 27. If ∂ is connected and preserves the path grading, then the filtration (1.25) induces a second quadrant spectral sequence whose first term is isomorphic to (Γ_{P}(E)(m, n), ∂_{0}) and which converges to H_{∗}(Γ_{P}(E)(m, n), ∂).

Proof. Under the assumptions of the proposition, the path grading is a ∂- invariant grading, compatible with the genus filtration (1.25), by finite dimensional pieces, see Proposition 22. This guarantees that the generally illbehaved second quadrant spectral sequence induced by (1.25) converges. The proof is finished by observing that the assumption that ∂ preserves the path grading implies that ∂_{0} = ∂_{D}. ⊓ ⊔

In most applications either ∂ is connected or ∂ = ∂_{D}, though there are also natural examples of PROPs with disconnected differentials, such as the deformation quantization PROP DefQ introduced by Merkulov in [16]. The following corollary immediately follows from Theorem 26(iii) and Proposition 27.

Corollary 28. Let P be a graded PROP concentrated in degree 0 and α : (Γ_{P}(E), ∂) → (P, 0) a homomorphism of dg PROPs. Suppose that α induces an isomorphism H_{0}(Γ_{P}(E), ∂) ≅ P and that Γ_{P}(E) is ∂_{0}-acyclic in positive degrees. Suppose moreover that either

(i) ∂ is connected and preserves the path grading, or

(ii) ∂(E) ⊂ Γ_{D}(E). Then α is a free resolution of the PROP P.

Remark 29. In Corollary 28 we assumed that the PROP P was concentrated in degree 0. The case of a general nontrivially graded non-differential PROP P can be treated by introducing the Tate-Jozefiak grading, as it was done, for example, for bigraded models of operads in [13, page 1481].

1.6 Minimal models of PROPs

In this section we show how the methods of this paper can be used to study minimal models of PROPs. Let us first give a precise definition of this object.

Definition 30. A minimal model of a dg PROP P is a dg free PROP (Γ_{P}(E), ∂) together with a homology isomorphism

P ⟵^{α} (Γ_{P}(E), ∂).

We also assume that the image of ∂ consists of decomposable elements of Γ_{P}(E) or, equivalently, that ∂ has no “linear part” (the minimality condition). Minimal models for \frac{1}{2} PROPs and dioperads are defined in exactly the same way, only replacing Γ_{P}(−) by Γ_{\frac{1}{2} P}(−) or Γ_{D}(−).

The above definition generalizes minimal models for operads introduced in [13]. While we proved, in [13, Theorem 2.1] that each operad admits, under some very mild conditions, a minimal model, and while the same statement is probably true also for dioperads, a similar statement for a general PROP would require some way to handle a divergence problem (see also the discussion in [14] and below).

Bialgebras. Recall that a bialgebra is a vector space V with an associative multiplication · : V ⊗ V → V and a coassociative comultiplication Δ : V → V ⊗ V which are related by

Δ(a · b) = Δ(a) · Δ(b), for a, b ∈ V.

The PROP B describing bialgebras has a presentation B = Γ_{P}( , )/I_{B}, where I_{B} denotes the ideal generated by

− ,  −  and − [figure] .

In the above display we denoted

:= ( ⊗ 11),  := (11 ⊗ ),  := ( ⊗ 11) ,  := (11 ⊗ ) ,
:= ∘ and [figure] := ( ⊗ ) ∘ σ(2, 2) ∘ ( ⊗ ),

where σ(2, 2) ∈ Σ_{4} is the permutation

σ(2, 2) = ( \begin{matrix}1 & 2 & 3 & 4 \\ 1 & 3 & 2 & 4 \end{matrix} ) .

As we argued in [14], the PROP B can be interpreted as a perturbation of the PROP \frac{1}{2}B = F (\frac{1}{2}b) for \frac{1}{2}bialgebras mentioned in Example 14. More precisely, let ϵ be a formal parameter, I_{B}^{ϵ} be the ideal generated by

− ,  −  and − ϵ [figure]

and B_{ϵ} := Γ_{P}( , )/I_{B}^{ϵ}. Then B_{ϵ} is a one-dimensional family of deformations of \frac{1}{2}B = B_{0} whose specialization (value) at ϵ = 1 is B. Therefore, every minimal model for B can be expected to be a perturbation of the minimal model for \frac{1}{2}B described in the following

Theorem 31 ([14]). The dg free PROP

(M, ∂_{0}) = (Γ_{P}(Ξ), ∂_{0}),  (1.26)

where the generators Ξ = Span({ξ_{m}^{n}}_{m,n∈I}) are as in Example 19 and the differential ∂_{0} is given by formula (1.15), is a minimal model of the PROP \frac{1}{2}B for \frac{1}{2}bialgebras.

Proof. Clearly, (M, ∂_{0}) = F (Ω_{\frac{1}{2} P}(Ass ∗ Ass^{†})). The theorem now follows from Theorem 18 (see also Example 19) and from the fact that the functor F preserves homology isomorphisms, see Corollary 5. ⊓ ⊔

The methods developed in this paper were used in [14] to prove:

Theorem 32. There exists a minimal model (M, ∂) of the PROP B for bialgebras which is a perturbation of the minimal model (M, ∂_{0}) of the PROP \frac{1}{2}B for \frac{1}{2}bialgebras described in Theorem 31,

(M, ∂) = (Γ_{P}(Ξ), ∂_{0} + ∂_{pert})

for some perturbation ∂_{pert} which raises the genus and preserves the path grading.

Proof. As shown in [14], a perturbation ∂_{pert} can be constructed using standard methods of the homological perturbation theory because we know, by Theorem 31, that Γ_{P}(Ξ) is ∂_{0}-acyclic in positive degrees. The main problem was to show that the procedure converges. This was achieved by finding a subspace X ⊂ Γ_{P}(Ξ) of special elements whose pieces X(m, n) satisfy the conditions that:

(i) each X(m, n) is a finite dimensional space spanned by G-monomials with connected G,

(ii) each X(m, n) is ∂_{0}-closed and ∂_{0}-acyclic in positive degrees, (iii) each X(m, n) is closed under vertex insertion (see below) and (iv) both and [figure] belong to X(2, 2).

Item (iii) means that X is stable under all derivations (not necessarily differentials) ω of Γ_{P}(Ξ) such that ω(Ξ) ⊂ X. The perturbation problem was then solved in X instead of Γ_{P}(Ξ). It remained to use, in an obvious way, Corollary 28(i) to prove that the object we constructed is really a minimal model of B. ⊓ ⊔

Dioperads. In this part we prove that the cobar duals of dioperads with a replacement rule induce, via functor F_{1} : diOp → PROP introduced in Section 1.1, minimal models in the category of PROPs. Since we are unable to prove the exactness of F_{1}, we will need to show first that these models are perturbations of minimal models of quadratic Koszul \frac{1}{2} PROPs and then use Corollary 28(ii). This approach applies to main examples of [4], i.e. Lie bialgebras and infinitesimal bialgebras.

Let P and Q be quadratic operads, with presentations P = Γ_{Op}(F)/(R) and Q = Γ_{Op}(G)/(S). We will consider dioperads created from P and Q by a dioperadic replacement rule. By this we mean the following.

As in Example 13, interpret F, G, R and S as bicollections. We already observed in Section 1.4 that

Γ_{D}(F, G)(2, 2) ≅ Γ_{\frac{1}{2} P}(F, G)(2, 2)⊕Ind_{\{1\}}^{Σ_{2}×Σ_{2}}(F ⊗G) ≅ G∘F ⊕Ind_{\{1\}}^{Σ_{2}×Σ_{2}}(F ⊗G), see also [4, Section 2.4] for details. The above decomposition is in fact a decomposition of Γ_{D}(F, G)(2, 2) into pth-homogeneous components, namely

G ∘ F = Span{f ∈ Γ_{D}(F, G)(2, 2); pth(f) = 4}

and

Ind_{{1}}^{Σ_{2}×Σ_{2}}(F ⊗ G) = Span{f ∈ Γ_{D}(F, G)(2, 2); pth(f) = 3}.

Given a (Σ_{2}, Σ_{2})-equivariant map

λ : G ∘ F → Ind_{{1}}^{Σ_{2}×Σ_{2}}(F ⊗ G),  (1.27)

one might consider a subspace

B = B_{λ} := Span{f − λ(f); f ∈ G ∘ F } ⊂ Γ_{D}(F, G)(2, 2)

and a quadratic dioperad

D_{λ} := Γ_{D}(F, G)/(R, B_{λ}, S).  (1.28)

We say that the map λ in (1.27) is a replacement rule [3, Definition 11.3], if it is coherent in the sense that it extends to a mixed distributive law between operads P and Q, see [3, Section 11] for details. An equivalent way to express this coherence is to say that D_{λ} and F_{2}(P ⋄ Q^{†}) are isomorphic as bicollections or, in the terminology of [4, Proposition 5.9], that D_{λ} ≅ P Q^{op}, see Proposition 17.

Example 33. An important example is given by an infinitesimal bialgebra (which we called in [3, Example 11.7] a mock bialgebra). It is a vector space V together with an associative multiplication · : V ⊗ V → V and a coassociative comultiplication Δ : V → V ⊗ V such that

Δ(a · b) = ∑ (a_{(1)} ⊗ a_{(2)} · b + a · b_{(1)} ⊗ b_{(2)})

for any a, b ∈ V.

The dioperad IB describing infinitesimal bialgebras is given by IB = Γ_{D}( , )/I_{IB}, where I_{IB} denotes the dioperadic ideal generated by

− ,  −  and − − .

The dioperad IB is created from two copies of the operad Ass for associative algebras using a replacement rule given by

λ( ) := + ,

see [3, Example 11.7] for details. As before, one may consider a one parameter family IB_{ϵ} := Γ_{D}( , )/I_{IB}^{ϵ}, where I_{IB}^{ϵ} is the dioperadic ideal generated by

− ,  −  and − ϵ ( + )

given by the one parameter family of replacement rules

λ_{ϵ}( ) := ϵ ( + ) .

Let IB := F_{1}(IB) be the PROP generated by the dioperad IB. It follows from the above remarks that IB is another perturbation of the PROP \frac{1}{2}B for \frac{1}{2}bialgebras.

Example 34. Recall that a Lie bialgebra is a vector space V, with a Lie algebra structure [−, −] : V ⊗ V → V and a Lie diagonal δ : V → V ⊗ V. As in Example 20 we assume that the bracket [−, −] is antisymmetric and satisfies the Jacobi equation and that δ satisfies the obvious duals of these conditions, but this time [−, −] and δ are related by

δ[a, b] = ∑ ([a_{(1)}, b] ⊗ a_{(2)} + [a, b_{(1)}] ⊗ b_{(2)} + a_{(1)} ⊗ [a_{(2)}, b] + b_{(1)} ⊗ [a, b_{(2)}])

for any a, b ∈ V, where we used, as usual, the Sweedler notation δa = ∑ a_{(1)}⊗ a_{(2)} and δb = ∑ b_{(1)} ⊗ b_{(2)}.

The dioperad LieB for Lie bialgebras is given by LieB = Γ_{D}( , )/I_{LieB}, where and are now antisymmetric generators and I_{LieB} denotes the ideal generated by

1 2 3 +_{2 3 1} +_{3 1 2} , ^{1 2 3} +^{2 3 1} +^{3 1 2} and _{1} _{2}^{1} ^{2} − _{2}_{1}^{2}^{1} −_{1} _{2}^{1} ^{2} + _{2}_{1}^{1}^{2} +_{1} _{2}^{2} ^{1} ,

with labels indicating, in the obvious way, the corresponding permutations of the inputs and outputs. The dioperad LieB is a combination of two copies of the operad Lie for Lie algebras, with the replacement rule

λ (_{1} _{2}^{1} ^{2} ) := _{2}_{1}^{2}^{1} +_{1} _{2}^{1} ^{2} − _{2}_{1}^{1}^{2} −_{1} _{2}^{2} ^{1} ,

see [3, Example 11.6]. One may obtain, as in Example 33, a one parameter family LieB_{ϵ} of dioperads generated by a one parameter family λ_{ϵ} of replacement rules such that LieB_{1} = LieB and LieB_{0} = \frac{1}{2}LieB := F_{2}(\frac{1}{2}lieb), where \frac{1}{2}lieb is the \frac{1}{2} PROP for \frac{1}{2}Lie bialgebras introduced in Example 20. Thus, the PROP LieB := F_{1}(LieB) is a perturbation of the PROP \frac{1}{2}LieB governing \frac{1}{2}Lie bialgebras.

Examples 33 and 34 can be generalized as follows. Each replacement rule λ as in (1.27) can be extended to a one parameter family of replacement rules by defining λ_{ϵ} := ϵ · λ. This gives a one parameter family D_{ϵ} := D_{λ_{ϵ}} of dioperads such that D_{1} = D_{λ} and D_{0} = P ⋄ Q^{†}. Therefore D_{λ} is a perturbation of the dioperad generated by the \frac{1}{2} PROP P ⋄ Q^{†}. This suggests that every minimal model of the PROP F_{1}(D_{λ}) is a perturbation of a minimal model for F_{2}(P⋄Q^{†}) which is, as we already know from Section 1.4, given by F_{2}(Ω_{\frac{1}{2} P}((P ⋄ Q^{†})^{!})) = F_{2}(Ω_{\frac{1}{2} P}(P^{!} ∗ (Q^{!})^{†})). The rest of this section makes this idea precise.

For any quadratic dioperad D, there is an obvious candidate for a minimal model of the PROP F_{1}(D) generated by D, namely the dg PROP Ω_{P}(D^{!}) = (Ω_{P}(D^{!}), ∂) := F_{1}((Ω_{D}(D^{!}), ∂)) generated by the dioperadic cobar dual Ω_{D}(D^{!}) = (Ω_{D}(D^{!}), ∂) of D^{!}.

The following proposition, roughly speaking, says that the dioperadic cobar dual of D_{λ} is a perturbation of the cobar dual of the \frac{1}{2} PROP (P ⋄ Q^{†})^{!} = P^{!} ∗ (Q^{!})^{†}.

Proposition 35. Let D = D_{λ} be a dioperad constructed from Koszul quadratic operads P and Q using a replacement rule λ. Consider the canonical decomposition

(Ω_{D}(D^{!}), ∂_{0} + ∂_{pth})

of the differential in the dioperadic bar construction (Ω_{D}(D^{!}), ∂). Then

(Ω_{D}(D^{!}), ∂_{0}) ≅ F_{2}(Ω_{\frac{1}{2} P}(P^{!} ∗ (Q^{!})^{†})).  (1.29)

Proof. We already observed that, in the terminology of [4], D ≅ P Q^{op}. This implies, by [4, Proposition 5.9(b)], that D^{!} ≅ (Q^{!})^{op} P^{!} which clearly coincides, as a bicollection, with our P^{!} ∗ (Q^{!})^{†}. The rest of the proposition follows from the description of D^{!} given in [4], the behavior of the replacement rule λ with respect to the path grading, and definitions. ⊓ ⊔

Remark 36. Since, as a non-differential dioperad, Ω_{D}(D) = Λ^{−1}Γ_{D}(↑ D̄^{∗}), where ↑ denotes the suspension of a graded bicollection, Λ^{−1} the sheared desuspension of a dioperad and D̄^{∗} the linear dual of the augmentation ideal of D, see Sections 1.4, 2.3, and 3.1 of [4] for details, the PROP (Ω_{P}(D), ∂) may be constructed from scratch as Ω_{P}(D^{!}) = Λ^{−1}Γ_{P}(↑ D̄^{∗}) with a differential coming from the “vertex expansion” (also called edge insertion). Thus, the PROP (Ω_{P}(D), ∂) may be thought of as a naive cobar dual of F_{1}(D), as opposed to the categorical cobar dual [6, Section 4.1.14].

Perhaps, one can successfully develop quadratic and Koszul duality theory for PROPs, using this naive cobar dual by analogy with [6, 4]. We are reluctant to emphasize (Ω_{P}(D), ∂) as a PROP cobar dual of the PROP F_{1}(D), because we do not know how this naive cobar dual is related to the categorical one.

The following theorem generalizes a result of Kontsevich [9] for D = LieB.

Theorem 37. Under the assumptions of Proposition 35, (Ω_{P}(D^{!}), ∂) is a minimal model of the PROP F_{1}(D).

Proof of Theorem 37. We are going to use Corollary 28(ii). It is straightforward to verify that H_{0}((Ω_{P}(D^{!}), ∂) ≅ F_{1}(D). Equation (1.29) gives

Ω_{P}(D^{!}) ≅ F (Ω_{\frac{1}{2} P}(P^{!} ∗ (Q^{!})^{†})),

therefore the ∂_{0}-acyclicity of Ω_{P}(D^{!}) follows from the exactness of the functor F stated in Theorem 4. ⊓ ⊔

Example 38. By Theorem 37, the dg PROP Ω_{P}(IB^{!}), where the quadratic dual IB^{!} of the dioperad IB for infinitesimal bialgebras is described in [4] as IB^{!} = Ass^{op} Ass, is a minimal model of the PROP IB = F_{1}(IB) for infinitesimal bialgebras. The dg PROP Ω_{P}(IB^{!}) has a form (Γ_{P}(Ξ), ∂_{0} + ∂_{pth}), where Ξ and ∂_{0} are the same as in Example 19. The path part ∂_{pth} of the differential is trivial on generators ξ_{n}^{m} with m + n ≤ 4, therefore the easiest example of the path part is provided by

∂( ) = ∂_{0}( ) + + + −

where

∂_{0}( ) = − +

is the same as in Example 19. We encourage the reader to verify that

pth( ) = pth( ) = pth( ) = pth( ) = 6, pth( ) = pth( ) = 5 and pth( ) = pth( ) = 4.

Similarly, the dg PROP Ω_{P}(LieB^{!}) = Ω_{P}(Com^{op} Com) is a minimal model of the PROP LieB := F_{1}(LieB) for Lie bialgebras.

1.7 Classical graph cohomology

Here we will reinterpret minimal models for the Lie bialgebra PROP LieB = F_{1}(LieB) and the infinitesimal bialgebra PROP IB = F_{1}(IB) given by Theorem 37 and Example 38 as graph complexes. The commutative case. Consider the set of connected (m, n)-graphs G for m, n ≥ 1 in the sense of Section 1.2. An orientation on an (m, n)-graph G is an orientation on ℝ^{v(G)} ⊕ ℝ^{m} ⊕ ℝ^{n}, i.e., the choice of an element in det ℝ^{v(G)} ⊗ det ℝ^{m} ⊗ det ℝ^{n} up to multiplication by a positive real number. This is equivalent to an orientation on ℝ^{e(G)} ⊕ H_{1}(|G|; ℝ), where e(G) is the set of (all) edges of G; to verify this, consider the cellular chain complex of the geometric realization |G| , see for example [18, Proposition B.1] and [15, Proposition 5.65].

Thus, an orientation on a connected (m, n)-graph G is equivalently given by an ordering of the set e(G) along with the choice of an orientation on H_{1}(|G|; ℝ) up to permutations and changes of orientation on H_{1}(|G|; ℝ) of even total parity. Consider the set of isomorphism classes of oriented (m, n)- graphs and take its k-linear span. More precisely, we should rather speak about a colimit with respect to graph isomorphisms, as in Section 1.2. In particular, if a graph G admits an orientation-reversing automorphism, such as the graph in Figure 1.3, then G gets identified with G^{−}, which will vanish after passing

[figure: •; •; •; •; •]

Fig. 1.3. A graph vanishing in the quotient by the automorphism group.

to the following quotient. Let G(m, n) be the quotient of this space by the subspace spanned by

G + G^{−} for each oriented graph G,

where G^{−} is the same graph as G, taken with the opposite orientation. Each space G(m, n) is bigraded by the genus and the number of interior edges (i.e., edges other than legs) of the graph. Let G_{g}^{q} = G_{g}^{q}(m, n) denote the subspace spanned by graphs of genus g with q interior edges for g, q ≥ 0. Computing the Euler characteristic of |G| in two ways, we get an identity |v(G)| − q = 1 − g. A graph G ∈ G_{g}(m, n) has a maximal number of interior edges, if each vertex of G is trivalent, in which case we have 3|v(G)| = 2q + m + n, whence q = 3g − 3 + m + n is the top degree in which G_{g}^{q}(m, n) ≠ 0.

Define a differential

∂ : G_{g}^{q} → G_{g}^{q+1},

so that ∂^{2} = 0, as follows:

∂G := ∑_{{G′ | G′/e=G}} G′,

where the sum is over the isomorphism classes of connected (m, n)-graphs G′ whose contraction along an edge e ∈ e(G′) is isomorphic to G. We will induce an orientation on G′ by first choosing an ordering of the set of edges of G and an orientation on H_{1}(|G|; ℝ) in a way compatible with the orientation of G. Then we will append the edge e which is being contracted at the end of the list of the edges of G. Since we have a canonical isomorphism H_{1}(|G′|; ℝ) →^{∼} H_{1}(|G|; ℝ), an orientation on the last space induces one on the first. This gives an orientation on G′. An example is given below.

∂ (_{1} _{2}^{1} ^{2} ) =_{1} _{2}^{1} ^{2} − _{2}_{1}^{2}^{1} −_{1} _{2}^{1} ^{2} + _{2}_{1}^{1}^{2} +_{1} _{2}^{2} ^{1}

In this figure we have oriented graphs, which are provided with a certain canonical orientation that may be read off from the picture. The rule of thumb is as follows. An orientation on the composition of two graphs is given by (1) reordering the edges of the first, lower, graph in such a way that the output legs follow the remaining edges, (2) reordering the edges of the second, upper, graph in such a way that the input legs precede the remaining edges, and (3) after grafting, putting the edges of the second graph after the edges of the first graph. The resulting ordering should look like this: the newly grafted edges in the middle, preceded by the remaining edges of the first graph and followed by the remaining edges of the second graph. We remind the reader that we place the inputs at the bottom of a graph and the outputs on the top.

Theorem 39. The graph complex in the commutative case is acyclic everywhere but at the top term G_{g}^{3g−3+m+n}. The graph cohomology can be computed as follows.

H^{q}(G_{g}^{∗}(m, n), ∂) = \{ \begin{matrix}LieB_{g}^{0}(m, n) & for q = 3g − 3 + m + n, \\ 0 & otherwise, \end{matrix}

where LieB_{g}^{0}(m, n) is the subspace of the (m, n)th component of the Lie bialgebra PROP LieB = F_{1}(LieB) consisting of linear combinations of connected graphs of genus g, see the presentation of the corresponding dioperad LieB in Example 34.

Remark 40. The acyclicity of the graph complex G_{g}^{∗}(m, n) has been proven in Kontsevich’s message [9], whose method we have essentially used in this paper.

Proof. The dioperad LieB may be represented as a product of the Lie operad Lie and the Lie co-operad Lie^{op}: LieB = Lie Lie^{op} — see [4, Section 5.2]. The dioperadic quadratic dual LieB^{!} is then Com^{op} Com, so that LieB^{!}(m, n) ≅ k with a trivial action of (Σ_{n}, Σ_{n}) for each pair (m, n), m, n ≥ 1. Then the subcomplex (Ω_{P}^{0}(LieB^{!}), ∂) ⊂ (Ω_{P}(LieB^{!}), ∂) spanned by connected graphs is isomorphic to the graph complex (G^{∗}(m, n), ∂). Now the result follows from Theorem 37. ⊓ ⊔ The associative case. Consider connected, oriented (m, n)-graphs G for m, n ≥ 1, as above, now with a ribbon structure at each vertex, by which we mean orderings of the set In(v) of incoming edges and the set Out(v) of outgoing edges at each vertex v ∈ v(G). It is convenient to think of an equivalent cyclic ordering (i.e., ordering up to cyclic permutation) of the set e(v) = In(v) ∪ Out(v) of all the edges incident to a vertex v in a way that elements of In(v) precede those of Out(v). Let RG(m, n) be the linear span of isomorphism classes of connected oriented ribbon (m, n)-graphs modulo the relation G + G^{−} = 0, with RG_{g}^{q}(m, n) denoting the subspace of graphs of genus g with q interior edges. The same formula

∂G := ∑_{{G′ | G′/e=G}} G′

defines a differential, except that in the ribbon case, when we contract an edge e ∈ e(G′), we induce a cyclic ordering on the set of edges adjacent to the resulting vertex by an obvious operation of insertion of the ordered set of edges adjacent to the edge e through one of its vertices into the ordered set of edges adjacent to e through its other vertex. An orientation is induced on G′ in the same way as in the commutative case. An example is shown in the following display.

∂( ) = − − + − + − − − − − −

A vanishing theorem, see below, also holds in the ribbon-graph case. The proof is similar to the commutative case: it uses Theorem 37 and the fact that IB = Ass Ass^{op} and IB^{!} = Ass^{op} Ass, see Example 38.

Theorem 41. The ribbon graph complex is acyclic everywhere but at the top term RG_{g}^{3g−3+m+n}. The ribbon graph cohomology can be computed as follows.

H^{q}(RG_{g}^{∗}(m, n), ∂) = \{ \begin{matrix}IB_{g}^{0}(m, n) & for q = 3g − 3 + m + n, \\ 0 & otherwise, \end{matrix}

where IB_{g}^{0}(m, n) is the subspace of the (m, n)th component of the infinitesimal bialgebra PROP IB = F_{1}(IB) consisting of linear combinations of connected ribbon graphs of genus g, see the presentation of the corresponding dioperad IB in Example 33.

Remark 42. Note that our notion of the genus is not the same as the one coming from the genus of an oriented surface associated to the graph, usually used for ribbon graphs. Our genus is just the first Betti number of the surface.

References

1. M. Aguiar, Infinitesimal Hopf algebras, New trends in Hopf algebra theory (La Falda, 1999), Contemporary Math., vol. 267, Amer. Math. Soc., 2000, p. 1–29.

2. M. Culler, K. Vogtmann, Moduli of graphs and automorphisms of free groups, Invent. Math. 84 (1986), p. 91–119.

3. T. Fox, M. Markl, Distributive laws, bialgebras, and cohomology, Operads: Proceedings of Renaissance Conferences (J.-L. Loday, J. Stasheff, A. Voronov, eds.), Contemporary Math., vol. 202, Amer. Math. Soc., 1997, p. 167–205.

4. W. Gan, Koszul duality for dioperads, Math. Res. Lett. 10 (2003), no. 1, p. 109– 124.

5. E. Getzler, M. Kapranov, Modular operads, Compositio Math. 110 (1998), no. 1, p. 65–126.

6. V. Ginzburg, M. Kapranov, Koszul duality for operads, Duke Math. J. 76 (1994), no. 1, p. 203–272.

7. M. Kontsevich, Formal (non)commutative symplectic geometry, The Gel’fand mathematics seminars 1990–1992, Birkhäuser, 1993.

8. M. Kontsevich, Feynman diagrams and low-dimensional topology, First European Congress of Mathematics II, Progr. Math., vol. 120, Birkhäuser, Basel, 1994.

9. M. Kontsevich, An e-mail message to M. Markl, November 2002.

10. S. Mac Lane, Natural associativity and commutativity, Rice Univ. Stud. 49 (1963), no. 1, p. 28–46.

11. I. Madsen, M. S. Weiss, The stable moduli space of Riemann surfaces: Mumford’s conjecture, Preprint math.AT/0212321, December 2002.

12. M. Markl, Cotangent cohomology of a category and deformations, J. Pure Appl. Algebra 113 (1996), no. 2, p. 195–218.

13. M. Markl, Models for operads, Comm. Algebra 24 (1996), no. 4, p. 1471–1500.

14. M. Markl, A resolution (minimal model) of the PROP for bialgebras, J. Pure Appl. Algebra 205 (2006), no. 2, p. 341–374.

15. M. Markl, S. Shnider, J. D. Stasheff, Operads in algebra, topology and physics, Mathematical Surveys and Monographs, vol. 96, American Mathematical Society, Providence, Rhode Island, 2002.

16. S. Merkulov, PROP profile of deformation quantization, Preprint

math.QA/0412257, December 2004.

17. R. Penner, Perturbative series and the moduli space of Riemann surfaces, J. Differential Geom. 27 (1988), no. 1, p. 35–53.

18. D. Thurston, Integral expressions for the Vassiliev knot invariants, Preprint

math.QA/9901110, January 1999.

19. B. Vallette, Dualité de Koszul des PROPs, Thesis, Université Louis Pasteur,