n-categorical pasting diagram overview

Question

There has been a lots of approaches to the notion of n-categorical diagram and n-categorical pasting diagram:

Street : "Parity complexes"

Power : " An n-categorical pasting theorem"

Johnson : "The combinatorics of n-categorical pasting"

Steiner : "Omega-category and chain complexes"

I'm wondering about the relations between these approaches.

It seem very clear for each of these how to translate from one approach to the other, but it is not obvious at all, and probably not true in general that these notion are exactly equivalent. In particular the way the "loop free" condition is formulated for each of these is rather subtle and they do not look equivalent.

Are there some known equivalences between these notions ? or maybe inclusion of some of them into others ? I would also be interested in examples that can be covered by one notion and not by the others...

Another way to put it: each notion of n-categorical diagram in the papers above define a class of polygraph, what are there known inclusion/equality between these classes.

Answer 1

I can provide some pieces of knowledge for Street and Johnson, and, to a lesser extent, for Steiner. Since my reputation on mathoverflow is not important enough, I am not able to include too many links and I can only cite figures in a master thesis I made for an internship on this subject : Parity complexes and pasting schemes

We can simplify the analysis of the structures given by Street and Johnson (and Steiner) by decomposing the problem with three questions :

1. (Globularity) How a globular structure suited for representing $\omega$-categories is built in these structures ?
2. (Loop-freeness) Since these structures are set-like (no multiple elements), how do these structures rule out categories with loops ? (Since we want these structures to represent polygraphs and that polygraphs are a notion of free-categories, either they must allow multiple elements, or they must rule out loops)
3. (Freeness / Segment condition) How do these structures achieve freeness in the polygraph sense ? In particular, how do the rules of these structures prevent blocked-morphism (non-trivial morphism that can not be decomposed) ? It seems that the solution to these problems rely heavily on what I call the segment condition.

Globularity

Street (and Steiner) uses cells structure to represent the morphisms. It is a stratified structure with $n+1$ levels for a cell of dimension $n$, that represent sources and targets in each dimension with "bags" of generators of dimension $i$ for level $i$. For each level $i$ for $0 \le i \le n$ there is a source bag and a target bag. The top level $n+1$ has only one bag. See figures 12 and 13.

Source and target operations then amount to remove some parts of the cells.

Concerning Johnson, morphisms are represented using closed set of generators (closed in the sense "source and target" closed) called well-formed pasting schemes (wfps). They lack the organization of cells but they represent much better what one imagines when thinking about pasting diagrams. On the other hand, source and target operations are less trivial : in order to get the source $s(A)$ of a wfps $A$, one removes the "inner-ends" of the top level generators, which is written $A - E(A)$. But this definition of source and target operations does not work for all categories. In particular, one must rule out some categories. For example (figure 20), the pasting scheme $A$ must be forbidden in Johnson because the source and target operations will not work properly on the pasting scheme since the node $1$ is at the same time a "inner-end" ($1 \in E(A)$) and a member of the source of $R(A)$. So $R(A) - E(R(A))$ would not be closed. In order to remove this problem, Johnson uses a strong axiom of acyclicity called the "no-direct-loops" condition, which prevents "inner-begins" to intersect with "inner-ends".

Loop-freeness

In order to get set-like structure which represents $\omega$-categories, one needs to rule out cycles in the composition of morphisms. One also needs to remove some more specific problems (see figure 15). All these problems can be ruled out using an acyclicity condition on $\triangleleft$, where $\triangleleft$ is the transitive closure of $\prec$, where $\prec$ represents some kind of contact between two generators.

In Street, a weak notion of contact is used, where $A \prec B$ when $A^+ \cap B^- \neq \emptyset$, that is to say when there is a contact between the ends of $A$ and the begins of $B$ at dimensions $n$ if $A$ and $B$ are of dimension $n+1$.

Johnson uses the same notion of contact for $\prec$ but asks for more than just the acyclicity condition on $\triangleleft$ (as mentionned in the Globularity section) : when $A \triangleleft B$, there must be no contacts between the inner-begins of $A$ and the inner-ends of $B$. It is loop-free axiom (i).

In Steiner, the acyclicity of $\triangleleft$ is a consequence of the definition of a loop-freeness basis. It is actually stronger than the acyclicity because this axiom also contains the "segment condition".

Freeness / Segment condition

In order to get a free-structures, we need to ensure that all cells / wfps can be written as a composition of generators. This can be false with only the acyclicity condition. That is why a "segment condition" is added. This segment condition says the following thing : let $x$ a generator of dimension $m$ and $S$ a $n$-morphism (or cell / pasting scheme) such that the $n$-source of $x$ can be pasted on $S$, then the contact zone must be a segment for $\triangleleft_S$

In Street, there is two occurences of this segment condition : as Proposition 1.3, which is a consequence of axiom 3 (b), and in the corrigenda as the new axiom asking tightness on the sets $\mu(x)$ (see correction of page 330) and its use through the new Proposition 1.4 (which states precisely a segment condition).

In Johnson, the segment condition appears as axiom (iv).

In Steiner, the segment condition is hidden in the loop-free basis axiom.

So, why do we need this segment condition ? Firstly, it is important to note that a formal composition of the generators of an $n$-surface $S$ should respect the order $\triangleleft_S$ to compose the generators : if $x \prec_S y$, then $x$ needs to be "activated" before $y$, because something in the source of $y$ is produced by $x$. Secondly, in an free $\omega$-category without loops, if a generator $x$ of dimension $m$ can be inserted in a context $E[\_]$ of dimension $n<m$ such that $E[x]$ exists, then there exists a formal decomposition of $\partial^-_n E[x]$ in which the $n$-generators of $\partial^-_n x$ appear as a segment in the decomposition (see figure 17). So, with these two facts, if we want the pasting of an $m$-generator on a $n$-surface to be compatible with an $\omega$-categorical structure, we need to require that generators can only be pasted on segments of $n$-surface.

If this hand-waving explanation is not convincing, let see what could go wrong. An example for Street can be found in the figure 18 : a 3-cell $\Gamma$ of source $X_1 \star X_4$ and of target $X_1' \star X_4'$ can be pasted on a 2-surface with generators $X_1 \prec X_2 \prec X_3 \prec X_4$. One can easily see that if we paste $\Gamma$ on the surface, we obtain a cell which is not decomposable, which is a problem, because the generators are not generating.

Note that this example does not work for Johnson, because the "no-direct-loops" condition is not satisfied for $X_2$ and $X_3$. But Power found in his paper a (complicated) example showing that the segment axiom was also necessary for Johnson. In a nutshell :

• there are 3-morphisms $H,H',K,K',F,F'$ which can be pasted together to form a 3-wfps $S$, which satisfy $F \prec K \prec H \prec H' \prec K' \prec F'$
• there is a 4-morphism $\Delta$ with $\Delta$ going from "$F+F'$" to "$\tilde{F}+\tilde{F}'$" which can be pasted on $S$. $F$ and $F'$ are essentially copies of $F$ and $F'$
• but if we paste on $S$, we get a pasting scheme which is not decomposable. Otherwise, by taking its source, we would get a composition of $S$ where $F$ and $F'$ appear as a segment in the composition order. But it is not possible, since $K,H,H',K'$ must appear between $F$ and $F'$ according to $\triangleleft_S$
• note that $\{F,F'\}$ is not a segment for $\triangleleft_S$. So this example is ruled out by Johnson loop-free axiom (iv)

In order to compare Street and Johnson on this particular point, I think that the segment property of Street is stronger than the one of Johnson, since loop-free (iv) asks a segment condition for generators that can be pasted on valid wfps, whereas for Street, the segment condition is true for generators pasted not only on cells, but on any well-formed set of generators. The advantage of Street is that the segment condition is more easily computable than the one of Johnson.

Street is not necessarily Johnson

Go back to figure 18 and consider all the generators except $\Gamma$. Then it is a sound parity complex, but it is not a pasting scheme because of $X_2$, $X_3$ and the "no-direct-loop" condition.

Johnson is not necessarily Street

See the pasting scheme on figure 19 which is ruled out as parity complex.

Generalization

Even though comparing the structures is important, I guess you would also be interested in the fact that Street and Johnson (and surely Steiner) are special cases of a "generalized parity complex". Starting from Street paper, one can easily simplify and generalize the work he has done. Here are the axioms of the structure :

• axiom 1 : $\triangleleft$ is acyclic
• axiom 2 (segment condition) : for all $n>k$, for all $x \in G_n$, and for all $k$-dimensional cell $D$ such that $\mu(x)_k \subset D_k$, then $\mu(x)_k$ is a segment for $\triangleleft_{D_k}$ (same with $\pi(x)_k$)
• axiom 3 : all elements are relevant (Street definition)

The details are inside the report.

Answer 2

The answer above by Simon does address Steiner's much newer and immensely more computable structure, the Augmented Directed Complexes, but he doesn't really cover its benefits over all of the previous methods. ADCs have been used to extend the lax/oplax tensor product to strict $\omega$-categories as well as the lax/oplax join and its various slice adjoints by Dimitri Ara and Georges Maltsiniotis because working with chain complexes of free modules is, all told, pretty easy.

It reduces a lot of the combinatorics of pasting to doing linear algebra in a chain complex of free abelian groups with a particular basis. The morphisms are just morphisms that preserve the free commutative monoids of 'positive elements' generated by the basis. Steiner does dip back into some of his earlier directed complex work in order to prove that Augmented Directed Complexes with a unital loop-free basis embed fully and faithfully into strict $\omega$-categories and are dense in it.

This answer is mostly supplementary to Simon's but if you're looking into working with pasting diagrams, I would highly highly recommend you look into the work of Steiner.

Also important is the fact that in Steiner's case, because the embedding is full and faithful, you can find 'relevant' elements as the images of maps from the ADC associated with an $n$-globe.

Edit: Avoid Steiner's 1993 version and read the 2004 version. They are (almost) totally unrelated. Basically, the 1993 version sort of describes the image of the embedding directly. It is not really useful for computation.