EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS
Vol. 12, No. 3, 2019, 734-748
ISSN 1307-5543 – www.ejpam.com
Published by New York Business Global

Labelled Maximal Tubings on Paths and Graph
Associahedra

S. Kaan Gürbüzer1, Bedia Akyar2,∗

1 Department of Mathematics, Dokuz Eylül University, İzmir, Turkey
2 Department of Mathematical Sciences, Aalborg University, Aalborg Ø, Denmark

Abstract. We determine the triangulation of a cyclohedron compatible with the Tamari order
on its faces. We define a name of a tubing on a path and a plumbing leading us to construct the
dendriform algebra of the collection of maximal tubings on paths. Moreover, we give an operad
structure of associahedra and a module structure of cyclohedra via tubings. We define labelled
maximal tubings on paths and give to an application of tubings in homological algebra.

2010 Mathematics Subject Classifications: 51M20, 13P20

Key Words and Phrases: Graph associahedra, dendriform algebra, triangulation, realization

1. Introduction

Stasheff [13] constructed the associahedron Kn as a space homeomorphic to an n-
dimensional unit cube, where Kn has a convex, curvilinear form. In the nineties, Shnider
and Sternberg [12] defined the associahedron Kn as a truncation of an n-simplex in Rn+1.
Carr and Devadoss [1] gave an alternative definition of Kn with respect to tubings to
obtain a family of polytopes, namely graph associahedron. Given any simple finite graph,
Devadoss [2] gave a realization of its corresponding graph associahedron and a geometric
meaning of every collection of tubings on graphs for a chosen suitable algorithm.

Loday [6] gave a simple realization of an associahedron by taking the convex hull of the
points corresponding to the set of planar binary trees. In addition, Loday [4] constructed
some operations mainly addition and multiplication on the set of planar binary trees and
also some algebraic structures such as Dendriform algebra of planar binary trees. On the
other hand, Forcey and Springfield [3] constructed a module on the vertices of cyclohedron
via tubings considering the relation between tubings and trees which enables to give a
geometrical view point for graded algebras. The product on a graded algebra turns into
the one on the vertices of a sequence of polytopes and this product is represented by the

∗Corresponding author.
DOI: https://doi.org/10.29020/nybg.ejpam.v12i3.3448

Email addresses: kaan.gurbuzer@deu.edu.tr (S. Kaan Gürbüzer),
bedia@math.aau.dk (Bedia Akyar)

http://www.ejpam.com 734 c© 2019 EJPAM All rights reserved.



S. K. Gürbüzer, B. Akyar / Eur. J. Pure Appl. Math, 12 (3) (2019), 734-748 735

sum of the vertices in higher dimensions. Since there exists a one to one correspondence
between the set of planar binary trees and the vertices of associahedra, the dendriform
algebra structure can also be considered on the vertices of associahedra.

Through the collection of planar rooted trees, Markl, Shnider and Stasheff [10] showed
that the sequence {Kn}n≥0 has an operad which is as an abstraction of a family of compos-
able functions of finitely many variables. Operads generalize various associativity proper-
ties that are already observed by modeling computational trees within algebra. Markl [8]
constructed a module structure over an operad and in [9], he showed that the sequence
{Wn}n≥0 of cyclohedra was not an operad but a module over the operad {Kn}n≥0. Briefly,
this module structure results from the indexes of the faces of the form Wn−k ×Kk−1 for
n ≥ k ≥ 1 and it enables us to generalize many types of graph associahedra.

In this paper, Section 2 contains an introduction on graph associahedra from Devadoss
[2] and the combinatorial properties of the faces of a graph associahedron from Forcey and
Springfield [3]. We give the triangulation of a cyclohedron compatible with the Tamari
order on its faces. In Section 3, we define a name of a tubing on a path as a sequence
of positive integers and establish some operations on tubings on paths. Furthermore, we
define a plumbing as a collection of maximal tubings with the sum and product operations.
We construct the dendriform algebra of the collection of maximal tubings on paths together
with the operations via names. After that, we determine the operad structure of the
sequence {Kn}n≥0 and interpret the module structure of the sequence {Wn}n≥0 defining
the comp maps and the cellular chain complex of an associahedron in terms of tubings.
In last section, as an application, we construct the chain complex whose boundary map is
defined on labelled maximal tubings on a path and compute its homology groups.

2. Graph Associahedron

For a finite simple graph G, Devadoss [2] defined a tube as a proper subset of nodes
of G whose induced graph is a connected subgraph of G. The graph G itself is called
the universal tube which is preferably not drawn.There are different positions of tubes
on a graph with respect to each other. In particular, two tubes t1, t2 are called nested if
t1 ⊂ t2 or t2 ⊂ t1; intersecting if they are not nested and t1 ∩ t2 6= ∅; adjacent if t1, t2
do not intersect and t1 ∪ t2 is again a tube; compatible if they are neither adjacent nor
intersect each other. A set of compatible tubes is called a tubing and it is assumed that
each tubing always contains the universal tube. If a graph G is a disconnected simple
graph with connected components G1, . . . , Gk then it is also assumed that a tubing does
not contain all the connected components. In general, a tubing on a graph with n nodes
is called k-tubing, 0 ≤ k ≤ n − 1, if it contains k tubes and universal tube. Especially,
(n − 1)-tubings are called the maximal tubings whose collection is denoted by MG. The
set of all tubings on a graph G is denoted by PG. This set becomes a partial ordered set
ordered by inclusion such that if T1, T2 ∈ PG and T1 can be obtained by deleting one or
more tubes in T2 then T2 < T1.

In [2], Devadoss proved that the poset PG admits a geometric realization KG, that
is, a convex polytope whose face poset is isomorphic to PG. The polytope KG is called



S. K. Gürbüzer, B. Akyar / Eur. J. Pure Appl. Math, 12 (3) (2019), 734-748 736

nested intersect adjacent compatible

Figure 1: Types of tubes

the graph associahedra associated to G. In order to obtain the geometric realization KG,
Devadoss produced a combinatorial way which relates the tubings in MG with the points
in space. He also proved that the convex hull of these points yields the graph associa-
hedra KG. For instance, the graph associahedra KG associated to the graph G with n
disconnected nodes is a simplex ∆n−1 in Rn given in terms of barycentric coordinates.
From another point of view, his method creates a system or a set of affine hyperplanes to
truncate the standart simplex. It is easily seen that these hyperplanes appear by adding
a new edge between two nodes in the graph and it causes new truncations in which new
faces appear.

A remarkable feature of a graph associahedra is that the faces of it can be obtained
by a product of other two graph associahedra. Carr and Devadoss described the face
structure of the graph associahedra KG in [1]. Given a graph G and a tube t on G, they
defined the reconnected complement graph G∗(t) of t in G as follows:

• Let V denote the set of nodes of G, then V \ t is the set of nodes of G∗(t).

• Let v1, v2 ∈ V \ t. There is an edge between v1 and v2 if either {v1, v2} or {v1, v2}∪ t
is connected in G.

Theorem 1. All facets of KG correspond to the set of 1-tubings. In particular, a facet
associated to a 1-tubing T = {G, t} is combinatorially equivalent to KG(t)×KG∗(t), where
KG(t) and KG∗(t) are graph associahedra corresponding to the tube t and the reconnected
complement of t in G, respectively.

One of the most well-known graph associahedra is the Stasheff polytope Kn−1, also
called associahedron. It becomes the realization of the poset PP(n), where P(n) denotes
an n-path which has n nodes labeled by the set {1, 2, . . . , n} with an increasing order.
The classical definition of an associahedron Kn is that it is an n-dimensional cell complex
whose cells are indexed by the meaningful bracketings of (n + 2) variables 1, . . . , n + 2.
This cell complex has a relation with the set of the planar rooted trees, Tree(n + 1),
with (n + 2) leaves. Each k-dimensional cell can be indexed by a rooted tree which has
(n + 2) leaves and (n − k + 1) internal vertices. Moreover, the vertices of Kn can be
indexed by the elements of the set Yn+1 of planar binary rooted trees. In [3], Forcey



S. K. Gürbüzer, B. Akyar / Eur. J. Pure Appl. Math, 12 (3) (2019), 734-748 737

and Springfield described a bijection between the set of planar rooted trees Tree(n) and
the set PP(n) of tubings on an n-path. The constructions of an associahedron given in
Loday [6], Markl [9] and Devadoss [2] have similarities on specifying the coordinates of

the vertices. Basically, Loday used the function f(n) =
n(n+ 1)

2
and Markl used an

exponential function f(n) = 3n. Devadoss [2] preferred to use an exponential function and
took attention to the chosen function which can cause deep cuts during the truncation
process of the simplex. In their methods, it can be easily seen that the boundary cells of
Kn are of the form Kp ×Kq, where p+ q = n− 1.

There is also another poset structure on the vertices of an associahedron. The partial
order in this structure is called the Tamari order on MP(n) and defined for two maximal
tubings T1, T2 in MP(n) such that T1 < T2 if T2 can be obtained from T1 by sliding a tube
from left to right. By using this poset structure, Loday [7] proved that an associahedron
Kn admits a triangulation by (n+ 1)n−1 simplices. This triangulation is compatible with
the Tamari order and one can also give an orientation to the facets of an associahedron
with respect to this order.

The second famous graph associahedra is so called cyclohedron Wn which appears in
the study on compactifications of configuration spaces of n distinct points on a circle.
With a view of the graph associahedra, an n-dimensional cyclohedron Wn is a geometric
realization of the poset PC(n + 1), where C(n + 1) denotes an oriented counterclockwise
cycle with n + 1-nodes labelled by the set {1, 2, . . . , n + 1}. A tube in a 1-tubing on an
(n + 1)-cycle can be seen as k-paths, where k = 1, . . . , n. This means that each 1-tubing
represents a face of a cyclohedron of the form Wn−k×Kk−1 and there are exactly n(n+1)
codimension one faces on Wn. In addition, there are exactly two types of tubes. The
tubes in the first type contain consecutive nodes and the tubes in the second type contain
the nodes of the form {1, 2, . . . , i, j, . . . , n}, where 1 ≤ i < i+ 1 < j ≤ n. One can call the
tubes in the second type as exotic tubes in the sense of the definition of exotic subintervals
in [9] given by Markl. It is clear that Wn can be combinatorially obtained by taking the
convex hull of n+ 1 disjoint copies of Kn−1 and also give an orientation on Wn using the
Tamari order on these copies of Kn−1. Hence we can get a triangulation of cyclohedron
similar to the once given by Loday for associahedron.

Theorem 2. The n-dimensional cyclohedron Wn admits a triangulation by (n+ 1)n sim-
plicies with respect to the orientation induced by the Tamari order on its faces.

Proof. By using induction on n, we assume that all the associahedral components
of the faces of cyclohedron are triangulated with respect to the Tamari order and take
cones over all the simplices on the faces with a common vertex as the barycenter of the
cyclohedron. Let dn denote the number of the simplices in the triangulation of Wn. If
n = 1, then it is clear that there are exactly 2 faces of the form W 0×K0 and there are only
two simplices in the triangulation. Suppose that for k < n, Wn−k admits a triangulation
by λn−k simplices. Then we show that Wn admits a triangulation by

λn =
n∑

k=1

(n+ 1)

(
n− 1

k − 1

)
λn−kk

k−2



S. K. Gürbüzer, B. Akyar / Eur. J. Pure Appl. Math, 12 (3) (2019), 734-748 738

=

n∑
k=1

(n+ 1)

(
n− 1

k − 1

)
(n− k + 1)n−kkk−2

= (n+ 1)
n−1∑
k=0

(
n− 1

k

)
(n− k)n−k−1(k + 1)k−1

= (n+ 1)(n+ 1)n−1 = (n+ 1)n.

simplices. The last row follows from the Abel’s equation for x−1(x + y + n − 1)n−1 with
x = 1, y = 1. For further details, see Riordan [11].

3. Operations on Tubes and Loday’s Dendriform Algebra

In this section, we define ”name” for a tubing on a path as a sequence of positive
integers for coding. We also define some new operations on the collection of maximal
tubings on a path motivated by Loday’s work [4]. These operations can be visualized as
binding or nesting two maximal tubings to get a bigger maximal tubing. We give the sum
and the product of maximal tubings as a collection of maximal tubings. Furthermore, we
interpret Loday’s dendriform algebra on the collection of maximal tubings.

Definition 1. The name of a tubing on an n-path is a finite sequence of positive integers
such that the j-th term of the sequence is the number of tubes including the universal ones
containing the j-th node of an n-path. Especially, the name of the tubing 0 on the empty
graph is 0. From now on, T = a1 . . . an denotes a tubing with the name representation.

32123

Figure 2: Example of the name of a tubing on 5-path

Remark 1. A tube t can be slided only in the smallest tube containing it. Let T1 = a1 . . . an
be a tubing and let t1 ∈ T1 be a tube. If the tube t2 ∈ T2 is obtained by sliding t1 ∈ T1 then
the name b1 . . . bn of T2 is

bi =


ai, i /∈ t1 ∪ t2;
ai, i ∈ t1 ∩ t2;
ai − 1, i ∈ t1 \ t2;
ai + 1, i ∈ t2 \ t1

for 1 ≤ i ≤ n.

Let T = a1 . . . an be a maximal tubing on an n−path, where ai = 1. The sequences
(a1−1) . . . (ai−1−1) and (ai+1−1) . . . (an−1) are still possible names of maximal tubings
on (i − 1)-path and (n − i)-path, respectively. Such a partition leads us an operation on
maximal tubings on paths.



S. K. Gürbüzer, B. Akyar / Eur. J. Pure Appl. Math, 12 (3) (2019), 734-748 739

Definition 2. Let T1 = a1 . . . am and T2 = b1 . . . bn be two tubings on an m-path and an
n-path, m,n > 0, respectively. The transition operation ”∨” between T1 and T2 is defined
by

T1 ∨ T2 = (a1 + 1) . . . (am + 1)1(b1 + 1) . . . (bn + 1)

and 0 ∨ T1 = 1(a1 + 1) . . . (am + 1) and T1 ∨ 0 = (a1 + 1) . . . (am + 1)1. It is easily seen
that T1 ∨ T2 is also a maximal tubing on an (m + n + 1)-path. This operation is neither
associative nor commutative. A remarkable feature of the transition operation is that, any
maximal tubing T can be divided into two parts, called left T l and right T r parts, from the
combining node.

Example 1. Let T l = 123 ∈MP(3) and T r = 2341 ∈MP(4) be given as on the left hand
side of Figure 3. The maximal tubing T = T l ∨ T r = 23413452 ∈ MP(8) can be obtained
by connecting these tubings via a new node.

∨ =

Figure 3: Example of the transition operation between the tubings

Definition 3. Let T1 = a1 . . . an ∈ MP(n) and T2 = b1 . . . bm ∈ MP(m) be maximal
tubings. The operations /, \ : MP(n) ×MP(m) → MP(n + m) are called before and
after operations and defined by

a1 . . . an/b1 . . . bm = (a1 + b1) . . . (an + b1)b1 . . . bm

a1 . . . an \ b1 . . . bm = a1 . . . an(b1 + an) . . . (bm + an)

Example 2. Let T1 = 231 ∈MP(3) and T2 = 3212 ∈MP(4) be given as on the left hand
side in Figure 4. We illustrate the before and after operations for T1 and T2 in Figure 4.

/

\

=

=

Figure 4: Before and after operations for the maximal tubings



S. K. Gürbüzer, B. Akyar / Eur. J. Pure Appl. Math, 12 (3) (2019), 734-748 740

Definition 4. The sum of two maximal tubings T1 and T2 is defined by

T1 + T2 :=
⋃

T1/T2≤T≤T1\T2

T

as a set of maximal tubings. Let n denote the degree of T ∈ MP(n) which is the number
of nodes in P(n). The degree of each maximal tubing in a sum of two maximal tubings
is the sum of the degrees of the terms. Furthermore, since 0 denotes the maximal tubing
without any node, its degree is considered as zero and hence 0 is the unit element with
respect to ” + ”.

Example 3. Let T1 = 123 and T2 = 212 be two maximal tubings of degree 3. The sum of
T1 and T2 is

T1 + T2 = {345212, 245312, 235412, 234512, 134523, 124534, 123545}.

Definition 5. A plumbing of degree n is a collection of maximal tubings in MP(n). We

denote the set of all plumbings of degree n by MP(n) and MP(∞) :=
⋃
n≥0

MP(n). The

addition operation on MP(∞) is obtained from the one + : MP(n)×MP(m)→MP(n+m)
which is defined by

∪iTi + ∪jTj := ∪i,j(Ti + Tj)

with the unit element 0.

We note that there is an involution of a tubing T in PP(n) denoted by T̄ . Let
T = a1 . . . an then T̄ = an . . . a1. The idea of involution can be extended to MP(∞) and
it makes MP(∞) an involutive graded monoid.

Theorem 3. Let T1, T2 and T3 be three maximal tubings. We have the following equalities

(T1/T2) \ T3 = T1/(T2 \ T3), T1/(T2 ∨ T3) = (T1/T2) ∨ T3, (T1 ∨ T2) \ T3 = T1 ∨ (T2 \ T3)

and

T1 ∨ T2 = T̄2 ∨ T̄1, T1/T2 = T̄2 \ T̄1, T1 \ T2 = T̄2/T̄1, T1 + T2 = T̄2 + T̄1

and also the inequalities

T ∨ T1 ≤ T ∨ T2, T1 ∨ T ≤ T2 ∨ T, T1/T ≤ T2/T, T \ T1 ≤ T \ T2

hold. In addition, for all T, T ′ ∈MP(n), if T ≤ T ′ then T̄ ′ ≤ T̄ .

Proof. Let T1 = a1 . . . an, T2 = b1 . . . bm and T3 = c1 . . . cl be maximal tubings. The
first three equalities directly follow from definition. The next three equalities are obtained
as follows:

T1 ∨ T2 = a1 . . . an ∨ b1 . . . bm = a1 . . . an1b1 . . . bm = bm . . . b11a1 . . . an = T̄2 ∨ T̄1,



S. K. Gürbüzer, B. Akyar / Eur. J. Pure Appl. Math, 12 (3) (2019), 734-748 741

T1/T2 = a1 . . . an/b1 . . . bm = (a1 + b1) . . . (an + b1)b1 . . . bm

= bm . . . b1(an + b1) . . . (a1 + b1) = bm . . . b1 \ an . . . a1 = T̄2 \ T̄1,
T1 \ T2 = a1 . . . an \ b1 . . . bm = a1 . . . an(b1 + an) . . . (bm + an)

= (bm + an) . . . (b1 + an)an . . . a1 = bm . . . b1/an . . . an = T̄2/T̄1.

The inequalities also directly follow from Definitions 2 and 3 and Remark 1. For the last
equality, we combine some of the equalities and the last two inequalities.

Theorem 4. Let T1 and T2 be two maximal tubings different from 0. The sum of T1 and
T2 is splitted into two parts as

T1 + T2 = (T1 + T l
2) ∨ T r

2 ∪ T l
1 ∨ (T r

1 + T2),

for T1 = T l
1 ∨ T r

1 and T2 = T l
2 ∨ T r

2 , where T l
i and T r

i are left and right parts of the tubing
respectively.

Proof. Let T1 = a1 . . . an ∈ MP(n) and T2 = b1 . . . bm ∈ MP(m) be two maximal
tubings such that ai = 1 and bj = 1. Now we have

T1 + T2 = {T ∈MP(n+m) | T1/T2 = (T1/T
l
2) ∨ T r

2 ≤ T ≤ T l
1 ∨ (T r

1 \ T2) = T1 \ T2}
= {T = c1 . . . cm+n ∈MP(n+m) |

(a1 + b1) . . . (an + b1)b1 . . . bm ≤ T ≤ a1 . . . an(b1 + an) . . . (bm + an)}.

From Definition 4, we directly observe that the tubes in T l
1 and T r

2 cannot be slided from
left to right. We assume that there exist two tubes t1 and t2 different from the universal
tube such that t1 /∈ T l

1 and t2 /∈ T r
2 contain all nodes in the tubes of T l

1 and T r
2 , respectively.

According to the compatibility condition, i-th and (n+j)-th nodes must be contained in t1
and t2, respectively. Since each tubing T in the sum (T1 +T2) is maximal, there must be a
node contained only by the universal tube and this node must be between i-th and (n+j)-
th nodes. This contradicts with ak ≥ 2 for k = i+ 1, . . . , n and bk ≥ 2 for k = 1, . . . , j− 1.
So there are exactly two types of tubings in (T1 + T2) in which the corresponding name
has either ci = 1 or cn+j = 1.

Now let us consider the first type of the tubings in T1+T2, where ci = 1. By definition,
the maximum of these tubings is T1 \T2 = a1 . . . an(b1+an) . . . (bm+an) but the minimum
one can only be the tubing a1 . . . ai(ai+1 + b1) . . . (an + b1)(b1 + 1) . . . (bm + 1) and the
rewriting the name of this tubing step by step as the following form

(a1 − 1) . . . (ai−1 − 1) ∨
(
(ai+1 + b1 − 1) . . . (an + b1 − 1)b1 . . . bm

)
=

(a1 − 1) . . . (ai−1 − 1) ∨
(
(ai+1 − 1) . . . (an − 1)/b1 . . . bm

)
=

T l
1 ∨ T r

1 /T2

gives that the set of tubings of the first type is {T ∈MP(n+m)|T l
1∨ (T r

1 /T2) ≤ T ≤ T l
1∨

(T r
1 \T2)}. Hence the set of tubings of the first type is the plumbing T l

1∨(T r
1 +T2). Similarly



S. K. Gürbüzer, B. Akyar / Eur. J. Pure Appl. Math, 12 (3) (2019), 734-748 742

for the tubings of the second type, the minimum tubing is T1/T2 and the maximum one is
(T1 \T l

2)∨T r
2 . So the set of tubings of the second type is {T ∈MP(n+m)|(T1/T l

2)∨T r
2 ≤

T ≤ (T1 \ T l
2) ∨ T r

2 } and clearly this set is the plumbing (T1 + T l
2) ∨ T r

2 .

Definition 6. Let T1 and T2 be two maximal tubings. The left sum and the right sum
of T1 and T2 are defined by T1 a T2 := T l

1 ∨ (T r
1 + T2) and T1 ` T2 := (T1 + T l

2) ∨ T r
2 ,

respectively. This can be extended over plumbings.

Proposition 1. The left and right sums of maximal tubings T1, T2 and T3 satisfy the
following relations

(T1 a T2) a T3 = T1 a (T2 + T3), (1)

(T1 ` T2) a T3 = T1 ` (T2 a T3), (2)

T1 ` (T2 ` T3) = (T1 + T2) ` T3 (3)

and 0 ` T = T = T a 0 for all T .

Proof. To prove (1), we do the following computation

(T1 a T2) a T3 = (T1 a T2)l ∨ ((T1 a T2)r + T3) = (T l
1 ∨ (T r

1 + T2))
l ∨ ((T l

1 ∨ (T r
1 + T2))

r + T3)

= T l
1 ∨ ((T r

1 + T2) + T3) = T l
1 ∨ (T r

1 + (T2 + T3)) = T1 a (T2 + T3).

For (2), we compute both sides and see that they are equal.

(T1 ` T2) a T3 = (T1 ` T2)l ∨ ((T1 ` T2)r + T3) (by definition of a)

= ((T1 + T l
2) ∨ T r

2 )l ∨ (((T1 + T l
2) ∨ T r

2 )r + T3) (by definition of `)

= (T1 + T l
2) ∨ (T r

2 + T3)

T1 ` (T2 a T3) = T1 ` (T l
2 ∨ (T r

2 + T3)) (by definition of a)

= (T1 + (T l
2 ∨ (T r

2 + T3)
l) ∨ (T l

2 ∨ (T r
2 + T3)

r (by definition of `)

= (T1 + T l
2) ∨ (T r

2 + T3)

Finally, for (3) we have the following equalities

T1 ` (T2 ` T3) = (T1 + (T2 ` T3)l) ∨ (T2 ` T3)r (by definition of `)

= (T1 + ((T2 + T l
3) ∨ T r

3 )l) ∨ ((T2 + T l
3) ∨ T r

3 )r (by definition of `)

= (T1 + ((T2 + T l
3)) ∨ T r

3 = ((T1 + T2) + T l
3) ∨ T r

3 = (T1 + T2) ` T3.

Corollary 1. Let T1 ∈MP(n), T2 ∈MP(m) be two maximal tubings. The left and right
sums satisfy

T1 ` T2 = T2 a T1 , T1 a T2 = T2 ` T1.

Definition 7. A unique way of writing T as a composition of n copies of the tubing
1 ∈ MP(1) with the left and right sums modulo the relations given in Proposition 1 is
called the universal expression of T ∈MP(n) and denoted by wT (1).



S. K. Gürbüzer, B. Akyar / Eur. J. Pure Appl. Math, 12 (3) (2019), 734-748 743

Example 4. The universal expression of T = 2132 is wT (1) = 1 ` 1 a (1 a 1).

Definition 8. Let T1 and T2 be any two maximal tubings. The product T1× T2 of T1 and
T2 is the ordered sum of the copies of T2 in the universal expression of T1. The product is
distributive from the left on each type of sums and it is not commutative. The product of
two maximal tubings can be extended to the product of plumbings.

Corollary 2. Let T1 = T l
1 ∨ T r

1 be a maximal tubing. The product can be given by the
formula

T1 × T2 = (T l
1 × T2) ` T2 a (T r

1 × T2)

and 0 × T2 = 0 for all maximal tubings T2. One also has T1 × T2 = T̄1 × T̄2 for any two
maximal tubings T1 and T2.

Now, we define the dendriform algebra on MP(∞).

Definition 9. A dendriform algebra is a vector space A equipped with two binary opera-
tions ≺,�: A⊗A→ A satisfying the following axioms

(a ≺ b) ≺ c = a ≺ (b ∗ c), (4)

(a � b) ≺ c = a � (b ≺ c), (5)

(a ∗ b) � c = a � (b � c) (6)

for all a, b, c ∈ A, where the operation ∗ defined by a ∗ b := a ≺ b+ a � b is associative.

Definition 10. Let F be a field and F [MP(∞)
′
] be the vector space generated by the

elements XT , for T ∈ MP(n) and n ≥ 1, that is, we do not consider the elements of the
form X0 = 1. Operations on F [MP(∞)

′
] are defined by

XT ≺ XT ′ : = XT`T ′ , (7)

XT � XT ′ : = XTaT ′ (8)

for any two maximal tubings T, T ′ and XT∪T ′ := XT +XT ′.

Proposition 2. The vector space F [MP(∞)
′
] equipped with the two operations ≺ and �

becomes a dendriform algebra by defining XT ∗ XT ′ = XT+T ′. The operations ≺ and �
can be partially extended to F [MP(∞)] as X0 � XT = XT = XT ≺ X0 for all T and
then F [MP(∞)] = F [MP(∞)

′
]⊕ F · 1 becomes an augmented unital associative algebra.

4. An Operad on Paths via Tubings

In [9], Markl gives a description of the cellular operad structure of associahedron.
Here we reconstruct it by using tubings on paths. In order to do that, first we define the
comp or composition maps on the collection {PP(n)}. Let T1 = a1 . . . an ∈ PP(n) and
T2 = b1b2 . . . bm ∈ PP(m). For n,m ≥ 1 and 0 ≤ i ≤ n, the comp map ◦i : PP(n) ×
PP(m)→ PP(n+m) is given by

T1 ◦i T2 = a1a2 . . . ai(b1 + ãi)(b2 + ãi) . . . (bm + ãi)ai+1 . . . an (9)



S. K. Gürbüzer, B. Akyar / Eur. J. Pure Appl. Math, 12 (3) (2019), 734-748 744

where ãi is the maximum of the integers ai, ai+1, that is, ãi = max(ai, ai+1), for 0 < i < n
and ã0 = a1 and ãn = an. It can be easily checked that for any three tubings T1, T2 and
T3, the comp map satisfies the following equations.

T1 ◦i (T2 ◦j T3) = (T1 ◦i T2) ◦j+i T3, 0 ≤ j ≤ m, (10)

(T1 ◦i T2) ◦j T3 = (T1 ◦j−m T3) ◦i T2, i+m+ 1 < j ≤ n+m. (11)

Since we shift the indices 1, one can think that they are different from the usual defi-
nition of comp maps in a non symmetric operad. But the operad structure of PP(∞) :=
{PP(m)}m≥1 with these comp maps has a one to one correspondence with the operad
structure of {Kn}n≥0. If we let the comp maps to be distributive over the union, then the
collection MP(∞) is closed under the comp maps ◦i. This property leads us to give the den-
driform operad {Dend(n)}n≥1 in terms of tubings on paths. The sequence {Dend(n)}n≥1
forms an operad whose i-th comp map ◦i : Dend(n) × Dend(m) → Dend(n + m − 1) is
defined by XT ◦i XT ′ = XT◦iT ′ , where Dend(n) = F [MP(n− 1)] for any field F.

Now, we construct the cellular chain complex of an associahedron in terms of tubings
on paths. Let T ∈ PP(n) be a k-tubing whose tubes are labelled by an order e1, . . . , ek
except the universal one. Two orderings ei1 , . . . , eik and ej1 , . . . , ejk are equivalent if they
are related by an even permutation. The equivalence class corresponding to an ordering
ei1 , . . . , eik is called the orientation and denoted by ei1 ∧ · · · ∧ eik = ω. An oriented k-
tubing T ∈ PP(n) with its orientation ω is a pair (T, ω). Let CCn−k(Kn) be a vector
space spanned by the oriented (n − k)-cells in Kn which are related by the oriented k-
tubings in PP(n+1) modulo the relation (T, ω1) = −(T, ω2), where ω1 and ω2 are distinct
orientations. The boundary operator on CC∗(K

n) is defined by

∂(T, ω) :=
∑

T ′={{1,...n+1},t1,...,tk+1}

(T ′, e′ ∧ ω) (12)

for oriented k-tubings on P(n + 1). This sum is taken over all (k + 1)-tubings such that
T = T ′ \ {ti} for some i = 1, . . . , k + 1 and e′ is the label of ti. The boundary map
∂ satisfies ∂2 = 0. Moreover, the comp maps in the operad {PP(n)}n≥1 can also be
extended on the oriented k-tubings with a sign convention. For 0 ≤ i ≤ n, the comp map
◦i : PP(n)× PP(m)→ PP(n+m) is given by

(T1, ω) ◦i (T2, ω
′) := (−1)(n+1)l+m(i+1)(T1 ◦i T2, ω ∧ ω′ ∧ e),

where T1, T2 are (n− k) and (m− l)-tubings and e denotes the label of the universal tube
of T2 and ω ∧ ω′ ∧ e is the consecutive composition of orientations.

Finally, we define a name of a tubing on a cycle as a finite sequence of positive integers
such that the j-th term of the sequence is the number of tubes containing the j-th node
of C(n). This leads us to construct the module structure of the collection {Wn}n≥0 via
tubings. The i-th (right) comp map ◦ri : PC(n)× PP(m)→ PC(n+m) is defined by

T2 ◦ri T1 = b1 . . . bi(a1 + b̃i) . . . (am + b̃i)bi+1 . . . bn,

where T1 = a1 . . . am ∈ PP(m), T2 = b1 . . . bn ∈ PC(n) and b̃i = max(bi, bi+1) for 1 ≤ i ≤
n− 1 and b̃i = max{b1, bn} for i = 0 and i = n.



S. K. Gürbüzer, B. Akyar / Eur. J. Pure Appl. Math, 12 (3) (2019), 734-748 745

Proposition 3. The collection PC(∞) := {PC(n)}n≥1 is a (right) module over the op-
erad PP(∞) := {PP(m)}m≥1. Clearly, this module structure is the same as the module
structure of {Wn}n≥0 over {Km}m≥0 in the sense of given in Markl [9].

5. On Integral Sequences via Tubings

In this section, we give the definition of a labelled maximal tubing on a path. We
work on a sequence in order to construct a chain complex and define the boundary map.
Finally, we compute the corresponding homology groups.

Definition 11. A labelled maximal tubing on a path is a maximal tubing such that each
tube is labeled by an element of a finite set I of indices.

Note that these elements are not necessarily distinct. A labelled maximal tubing can
be considered as a pair (T, f) such that f : T → I maps a tube to its label. Clearly,
there is a bijection between the set of labelled maximal tubings on P(n) and MP(n)× In.
In particular, MP(2) has only two elements whose names are 21 and 12 and there are
exactly two types of labelled maximal tubings in MP(2)× I2 such that either of the form
(21, i1, i2) or (12, i1, i2).

Definition 12. The nested tubes t1 and t2 in a maximal tubing T ∈ MP(n) such that
t1 ⊂ t2 are called local pattern in the sense of Loday [5] if there is no any tube t such that
t1 ⊂ t ⊂ t2.

In order to construct a chain complex, we define a sequence S = {Sn × In}n≥0 by an
induction on n as follows: By convention, we assume that S0×I0 = MP(0)×I0, S1×I1 =
MP(1)× I, S2× I2 ⊂MP(2)× I2. A labelled maximal tubing T is in Sn× In if and only
if all local patterns of T illustrated either by the form 21 or 12 are in S2. The alternating
series of the sequence S is determined by the numbers of elements in Sn × In as follows:

f(S, t) =
∑
n≥0

(−1)n+1(#(Sn × In)) tn+1.

Let Z = {Zn × In} be another sequence such that Z2 × I2 is the complement of S2 × I2
in MP(2) × I2 which implies that a labelled maximal tubing T is in Zn × In if it has a
local pattern which is not contained in S2 × I2.

Now, we define a chain complex C∗ = (Cn, ∂)n≥0 over a field F. The space of n chains
is defined by

Cn =
⊕

i0,...,in

F [Zn × Si0 × · · · × Sin ]

where ij ≥ 0. A vector ω := (zn, Ti0 , . . . , Tin) in F [Zn × Si0 × · · · × Sin ] is of the form

ω =

(
. . .
((
zn ◦0 Ti0

)
◦i0+1 Ti1

)
. . .

)
◦
(

n−1∑
k=0

ik + 1)

Tin



S. K. Gürbüzer, B. Akyar / Eur. J. Pure Appl. Math, 12 (3) (2019), 734-748 746

The boundary map of the complex is defined by

∂ =

n∑
k=1

(−1)kdk, (13)

where dkω = dk(zn;T0, . . . , Tn) = 0 if the minimal tube containing the k-th node in zn is
not a cup, that is, it contains only one node and otherwise dkω = (εk(zn), T0, . . . , Tk−1 ∨
Tk, . . . , Tn) where εk deletes the k-th node and the cup containing it in zn. Note that the
label of the tube covering Tk−1 ∨ Tk is the label of the deleted cup in zn. If Tk−1 ∨ Tk
contains a local pattern in Z then dk(zn, T0, . . . Tn) = 0. The complex C∗ is called the
Koszul complex of S.

Proposition 4. The boundary map ∂ satisfies the boundary condition ∂2 = 0.

Proof. Let ω = (zn, T0, . . . , Tn). We need to prove that dkdj = dj−1dk for k < j. If
k < j − 1, we have the following three cases.

• If zn does not have a cup at the k-th node then dkdj = dj−1dk = 0.

• If zn does not have a cup at the j-th node then dkdj = 0 and by renumbering the
maximal tubings we get dj−1dk = 0.

• If zn does not have a cup neither at the k-th nor j-th nodes then

dkdj(zn, T0, . . . , Tn) = dk(εj(zn), T0, . . . , Tj−1 ∨ Tj , . . . , Tn)

= (εkεj(zn), T0, . . . , Tk−1 ∨ Tk, . . . , Tj−1 ∨ Tj , . . . , Tn)

= (εj−1εk(zn), T0, . . . , Tk−1 ∨ Tk, . . . , Tj−1 ∨ Tj , . . . , Tn)

= dj−1(εk(zn), T0, . . . , Tk−1 ∨ Tk, . . . , Tn)

= dj−1dk(zn, T0, . . . , Tn)

For k = j − 1, we examine dkdk+1 and dkdk. It is clear that dkdk = 0 because εk(zn)
cannot have a cup at the k-th node. On the other hand, if zn does not have a cup at the
(k + 1)-st node then dkdk+1 = 0, otherwise

dkdk+1(ω) = (εkεk+1(zn), T0, . . . , Tk−1 ∨ (Tk ∨ Tk+1), . . . , Tn)

since εk+1(zn) have a cup at the k-th node. The universal tubes of Tk∨Tk+1 and Tk−1∨(Tk∨
Tk+1) constitute a local pattern with the labels of the cups in zn. Hence Tk−1∨ (Tk∨Tk+1)
is in Z which gives that dkdk+1(ω) = 0.

Definition 13. The basis vector ω = (zn, T0, . . . , Tn) is called an extremal vector with i
cups in zn for each n ≥ 0 and 0 < i < n if there is no any element ω′ such that dk(ω′) = ω
for some k ≥ 0.

Proposition 5. For each extremal vector ω with k cups, the subcomplex Cω spanned by
the basis vectors di1 . . . dirω, r ≤ k, is isomorphic to the augmented chain complex of the
standard simplex ∆k−1.



REFERENCES 747

Proof. The graded subvector space of C∗ spanned by the elements di1 . . . dirω is stable
by ∂ and forms a subcomplex. The bijection between the cells of ∆k−1 and the set of
non-zero vectors {di1 . . . dirω} is constructed by sending the (j − 1)-st vertex of ∆k−1 to
the vector di1 . . . d̂ij . . . dikω where ij is the j-th cup of zn. Here the vertices of ∆k−1 are
enumerated by 0 to (k − 1). This leads us that the boundary map on the chain complex
of the standart simplex corresponds to the boundary map ∂ defined in (13).

Proposition 6. The chain complex C∗ is isomorphic to
⊕
ω

Cω for all extremal vectors

ω.

Proof. If a vector ω ∈ C∗ is an extremal vector, then it is clear that ω ∈ Cω. Otherwise,
there exists an extremal vector ω1 such that di1di2 . . . dir(ω1) = ω for some ij , where
1 ≤ j ≤ r and it gives that ω ∈ Cω1 .

Now, we want to prove that any basis vector belongs to one and only one subcomplex
of the form Cω, that is, if a basis vector belongs to both Cω and Cω1 then we want
to show that ω = ω1. Let ω = (zn, T0, . . . , Tn) and ω1 = (z′n, T

′
0, . . . , T

′
n) be given. If

di(ω) = dj(ω1) 6= 0, then the i-th node is contained by a cup in zn and the j-th node is
contained by a cup in z′n such that εi(zn) = εj(z

′
n). If i < j, then there exists ω̂ such that

dj(ω̂) = ω and di(ω̂) = ω1. Therefore ω and ω1 are not extremal which follows that i = j.
In other words,

di(ω) = di(ω1) = (εi(z), T0, . . . , Ti−1 ∨ Ti, . . . , Tn). (14)

The only vector is (zn, T0, . . . , Tn) satisfying (14) and therefore ω = ω1.

Proposition 7. The complex C∗ is acylic for any choice of a sequence S, that is, Hn(C∗) =
0 for all n > 0 and H0(C∗) = F.

Proof. By Propositions 5 and 6 the homology of the complex is trivial because the
standart simplex is contractible. There is only one exception in dimension 0 because the
subcomplex corresponding to the element ω = (0,0) is F in dimension 0. So we have
Hn(C∗) = 0 for all n > 0 and H0(C∗) = F.

Proposition 8. The Poincare series of the complex C∗ is equal to f(Z, f(S, t)). This also
gives that if Z2 × I2 is the complement of S2 × I2 in MP(2)× I2 then f(Z, f(S, t)) = t.

Proof. By the construction of the complex C∗, it is clear that the Poincare series of
the complex C∗ is equal to f(Z, f(S, t)). Since the Poincare series of a complex is the same
as the Poincare series of its homology and using Proposition 7, f(Z, f(S, t)) becomes an
identity polynomial on the variable t.

References

[1] M. P. Carr and S. L. Devadoss. Coxeter complexes and graph-associahedra. Topology
Appl., 153(12):2155–2168, 2006.



REFERENCES 748

[2] S. L. Devadoss. A realization of graph associahedra. Discrete Mathematics, 309(1):271
– 276, 2009.

[3] S. Forcey and D. Springfield. Geometric combinatorial algebras: Cyclohedron and
simplex. Journal of Algebraic Combinatorics, 32(4):597–627, 2010.

[4] J. L. Loday. Arithmetree. Journal of Algebra, 258(1):275 – 309, 2002.

[5] J. L. Loday. Inversion of integral series enumerating planar trees. Séminaire
Lotharingien de Combinatoire, 53:16, 2004.

[6] J. L. Loday. Realization of the stasheff polytope. Archive der Mathematik, (83):267–
278, 2004.

[7] J. L. Loday. Parking functions and triangulation of the associahedron. In Cate-
gories in algebra, geometry and mathematical physics, Volume 431 of Contemporary
Mathematics, pages 327–340. American Mathematical Society, Providence, RI, 2007.

[8] M. Markl. Models for operads. Communications in Algebra, 24(4):1471–1500, 1996.

[9] M. Markl. Simplex, associahedron, and cyclohedron. In Higher homotopy structures
in topology and mathematical physics (Poughkeepsie, NY, 1996), Volume 227 of Con-
temporary Mathematics, pages 235–265. American Mathematical Society, Providence,
RI, 1999.

[10] M. Markl, S. Shnider, and J. Stasheff. Operads in algebra, topology and physics.
Mathematical surveys and monographs. American Mathematical Society, 2007.

[11] J. Riordan. Combinatorial identities. R. E. Krieger Pub. Co., 1979.

[12] S. Shnider and S. Sternberg. Quantum groups. Graduate Texts in Mathematical
Physics, II. International Press, Cambridge, MA, 1993. From coalgebras to Drinfel’d
algebras, A guided tour.

[13] J. Stasheff. Homotopy associative h-spaces i. II, Transactions of the American Math-
ematical Society, (108):275–312, 1963.