nLab pasting scheme



Higher category theory

higher category theory

Basic concepts

Basic theorems





Universal constructions

Extra properties and structure

1-categorical presentations



Pasting schemes are one possibility to give a rigorous treatment of the (older) notational device of pasting diagrams.

Notions of pasting scheme

More than one definition of pasting scheme has been used to give a justification to the practice of pasting diagrams.

For example, there are pasting schemes in the sense of Johnson 1987, and there are pasting schemes in the sense of Power 1990.

Power’s definition

Power’s notion is based on planar embeddings of quivers QQ that satisfy the following conditions:

  • QQ is finite and connected;

  • For the free category F(Q)F(Q) generated by QQ, every endomorphism is an identity (QQ has no directed cycles);

  • There are vertices s,ts, t of QQ (the source and sink, respectively) such that for every vertex vv, the hom-sets F(Q)(s,v)F(Q)(s, v) and F(Q)(v,t)F(Q)(v, t) are inhabited (there exist directed paths in QQ from ss to vv and from vv to tt).

We will call such quivers progressive, in rough analogy with progressive string diagrams.

There is a restricted geometric realization functor

Quiv=Set (01) opskelSet Δ opRSpaceQuiv = Set^{(0 \rightrightarrows 1)^{op}} \stackrel{skel}{\to} Set^{\Delta^{op}} \stackrel{R}{\to} Space

(into a convenient category of topological spaces SpaceSpace) which we again denote as R:QuivSpaceR: Quiv \to Space.


(after Power) A pasting scheme consists of a progressive quiver QQ together with an subspace embedding i:R(Q) 2i: R(Q) \hookrightarrow \mathbb{R}^2, such that ii is a C 1C^1 embedding on each edge interior.

To each pasting scheme (Q,i)(Q, i) we may associate a 2-computad C=Comp(Q,i)C = Comp(Q, i). Part of the computad structure is easily described:

  • The underlying quiver of CC is QQ;

  • The elements of C 2C_2 (the 2-cells) are the bounded connected components of 2i(R(Q))\mathbb{R}^2 \setminus i(R(Q)).

To complete the description of the computad, we need to define the source and target σ(c),τ(c)Mor(F(Q))\sigma(c), \tau(c) \in Mor(F(Q)) of a 2-cell cc. For each edge eQ 1e \in Q_1 such that i(e)i(e) lies in the boundary of cc, and each interior point xex \in e, we let t(x)=i(x)t(x) = i'(x) be the tangent vector, and n(x)n(x) the inward-pointing normal (pointing into cc); the C 1C^1 embedding condition ensures that these make sense. Then say that ee is a negative edge of cc if

det(t(x)n(x))<0\det \binom{t(x)}{n(x)} \lt 0

(the cell cc is “to the right” as ii is traversed along ee) and a positive edge if

det(t(x)n(x))>0\det \binom{t(x)}{n(x)} \gt 0

(the cell cc is to the left).

Power shows that under the progressivity conditions, for each cC 2c \in C_2 there are unique distinct vertices u,vu, v such that the negative edges of cc form a directed path αF(Q)(u,v)\alpha \in F(Q)(u, v) from uu to vv, and the positive edges of cc form a directed path βF(Q)(u,v)\beta \in F(Q)(u, v). We then define σ(c)=α\sigma(c) = \alpha and τ(c)=β\tau(c) = \beta.

Power’s pasting theorem may be stated in the following form:


For every pasting scheme (Q,i)(Q, i), the free 2-category on the 2-computad Comp(Q,i)Comp(Q, i) has exactly one 2-morphism γ\gamma whose 00-domain is the source of QQ, whose 00-codomain is the sink of QQ, whose 11-domain of γ\gamma is the directed path consisting of positive edges of the unique unbounded component of 2i(R(Q))\mathbb{R}^2 \setminus i(R(Q)), and whose 11-codomain is the directed path consisting of negative edges of that component.


The notion of pasting in a 2-category was introduced in

  • Jean Bénabou, Introduction to bicategories, in Lecture Notes in Mathematics Vol. 47, pp. l-77, Springer-Verlag, New York/Berlin, (1967)

  • Michael Johnson: Pasting Diagrams in nn-Categories with Applications to Coherence Theorems and Categories of Paths, Doctoral Thesis, University of Sydney, 1987

  • Michael Johnson: The Combinatorics of nn-Categorical Pasting, Journal of Pure and Applied Algebra 62 (1989)
  • John Power: A 2-Categorical Pasting Theorem, Journal of Algebra 129 (1990)

Other notions of pasting presentations have been given by Street (parity complexes) and by Steiner,

  • Ross Street, Parity complexes, Cahiers Top. Géom Diff. Catégoriques 32 (1991), 315-343. (link) Corrigenda, Cahiers Top. Géom Diff. Catégoriques 35 (1994), 359-361. (link)

  • Richard Steiner, The algebra of directed complexes, Appl. Cat. Struct. 1 (1993), 247-284.

Last revised on August 6, 2017 at 18:54:49. See the history of this page for a list of all contributions to it.