Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

• Forgot your password?
• Apply for membership

1. • CommentRowNumber1.
   • CommentAuthorPeter Heinig
   • CommentTimeJul 18th 2017
   • (edited Jul 18th 2017)
   • PermaLink
   Author: Peter Heinig
   Format: MarkdownItex[Reasons for starting a new thread: (0) This topic seems fundamental and complex enough to merit a thread of its own. (1) This topic seems be likely to be of lasting interest to others in the nLab. (2) The relevant threads that exist tend to be *LatestChanges* threads and so far, no change was meant on account of t*his* topic. ] Briefly: is planarity *only-sufficient* for a rigorous formalization of pasting schemes in 2-, 3- and 4-categories, or is there something more essential that I am missing, causing mathematicians to use plane graphs when doing so? In more detail: my understanding is that A. J. Power in "A 2-Categorical Pasting Theorem Journal of Algebra 129, 439-445 (1990), henceforth JAlg129, gave the first rigorous proof that any order in which one tries to evaluate a given finite acyclic plane pasting diagram evaluates to the same 2-cell. It indeed seems to be the case that (telling from what I studied of work of N. Gurski and others) for 2- and 3-categories, and even (telling from what I studied of work of T. Trimble and A. E. Hoffnung, and from in particular Trimble's diagrams hosted by J. Baez) for 4-categories, all axioms necessary to construct these structures *can* be expressed by "schemes" whose underlying graphs *happen* to be planar. But is there a precise sense because of which one can discount the possibility that one * might need/want pasting-scheme-equation-expressed-axioms whose underlying graphs are *non*planar? It seems to depend on the answer to this question whether one considers the formal definitions of "pasting diagram" and "pasting scheme", which are plane graphs with some additional structure added, as fundamental or merely manageable expedients sufficient to rigorously formalize *those*pasting-diagram-challenges that had been thrown down so far, so to speak. Another aspect is that some graph-theorists might disagree that Power's proof makes "heavy use of the techniques of Graph Theory" (JAlg129, abstract); the proof rather makes essential use of the *plane* graphs, i.e., is rather an application of planarity than of what is typically seen as graph theory. While "heavy use" is an overstatement in my opinion, this seems a nice example of *common ground* between category theory and graph theory. It apparently has not been made clear enough what is necessary for what. I did not yet look closely into the question how much of the planarity is *indispensable* for Power's proof to work out, and decided to ask first since this seems an obvious question and likely to have been asked answered before, but I do not find it. The *obvious* question is of course: is there a non-planar relevant counterexample in the literature? I have been searching around for quite some time now. It seems to me that, roughly speaking, one can *decide* to impose *additional non-planar axioms*, although one just happens not to need to do so in order to ensure coherence. So, do you think Power and Yetter just *happened to tame higher-composition restricted to the plane*, using the plane as a convenient frame in which to carry out the induction-proof, or am I missing something essential because of which one can rest assured that no *non-planar* "pasting diagrams" (the latter in an informal sense) will be needed? If not, the right formalization of pasting diagrams and nonambiguity of composition might perhaps not yet have been found.

   [Reasons for starting a new thread:

   (0) This topic seems fundamental and complex enough to merit a thread of its own.

   (1) This topic seems be likely to be of lasting interest to others in the nLab.

   (2) The relevant threads that exist tend to be LatestChanges threads and so far, no change was meant on account of this topic.

   ]

   Briefly: is planarity only-sufficient for a rigorous formalization of pasting schemes in 2-, 3- and 4-categories, or is there something more essential that I am missing, causing mathematicians to use plane graphs when doing so?

   In more detail: my understanding is that A. J. Power in “A 2-Categorical Pasting Theorem Journal of Algebra 129, 439-445 (1990), henceforth JAlg129, gave the first rigorous proof that any order in which one tries to evaluate a given finite acyclic plane pasting diagram evaluates to the same 2-cell.

   It indeed seems to be the case that (telling from what I studied of work of N. Gurski and others) for 2- and 3-categories, and even (telling from what I studied of work of T. Trimble and A. E. Hoffnung, and from in particular Trimble’s diagrams hosted by J. Baez) for 4-categories, all axioms necessary to construct these structures can be expressed by “schemes” whose underlying graphs happen to be planar.

   But is there a precise sense because of which one can discount the possibility that one

   • might need/want pasting-scheme-equation-expressed-axioms whose underlying graphs are nonplanar?

   It seems to depend on the answer to this question whether one considers the formal definitions of “pasting diagram” and “pasting scheme”, which are plane graphs with some additional structure added, as fundamental or merely manageable expedients sufficient to rigorously formalize thosepasting-diagram-challenges that had been thrown down so far, so to speak.

   Another aspect is that some graph-theorists might disagree that Power’s proof makes “heavy use of the techniques of Graph Theory” (JAlg129, abstract); the proof rather makes essential use of the plane graphs, i.e., is rather an application of planarity than of what is typically seen as graph theory.

   While “heavy use” is an overstatement in my opinion, this seems a nice example of common ground between category theory and graph theory. It apparently has not been made clear enough what is necessary for what.

   I did not yet look closely into the question how much of the planarity is indispensable for Power’s proof to work out, and decided to ask first since this seems an obvious question and likely to have been asked answered before, but I do not find it.

   The obvious question is of course: is there a non-planar relevant counterexample in the literature? I have been searching around for quite some time now.

   It seems to me that, roughly speaking, one can decide to impose additional non-planar axioms, although one just happens not to need to do so in order to ensure coherence.

   So, do you think Power and Yetter just happened to tame higher-composition restricted to the plane, using the plane as a convenient frame in which to carry out the induction-proof, or am I missing something essential because of which one can rest assured that no non-planar “pasting diagrams” (the latter in an informal sense) will be needed?

   If not, the right formalization of pasting diagrams and nonambiguity of composition might perhaps not yet have been found.

2. • CommentRowNumber2.
   • CommentAuthorUrs
   • CommentTimeJul 18th 2017
   • PermaLink
   Author: Urs
   Format: MarkdownItex> (telling from what I studied of work of T. Trimble and A. E. Hoffnung, and from in particular Trimble’s diagrams hosted by J. Baez) for 4-categories, all axioms necessary to construct these structures can be expressed by “schemes” whose underlying graphs happen to be planar. Er? Those notes by Todd ([here](https://ncatlab.org/nlab/show/tetracategory#references)) display higher dimensional diagrams, notice the triple arrows. The 3d diagram takes up several 2d pages.

   (telling from what I studied of work of T. Trimble and A. E. Hoffnung, and from in particular Trimble’s diagrams hosted by J. Baez) for 4-categories, all axioms necessary to construct these structures can be expressed by “schemes” whose underlying graphs happen to be planar.

   Er? Those notes by Todd (here) display higher dimensional diagrams, notice the triple arrows. The 3d diagram takes up several 2d pages.

3. • CommentRowNumber3.
   • CommentAuthorPeter Heinig
   • CommentTimeJul 18th 2017
   • (edited Jul 18th 2017)
   • PermaLink
   Author: Peter Heinig
   Format: MarkdownItexRe #2. Thanks for pointing out, I was referring to the planar pasting schemes which are connected by the triple-arrows. The "role" of planarity remains not clear (to me). I am aware that the skeleton associahedron (apparently) ceases to be a planar from from $n=6$ onwards. Naively, isn't it natural to * expect Power in his article to proactively comment on the role of planarity; his exposition is, roughly, "Bénabou introduced (something formalizable by) planar pasting schemes, and here is a proof that his concept is consistent/coherent." (Perhaps Power was assuming readers to be well-versed in the combinatorial attempts that he is hinting at in his introduction, Johnson etc.---I recognized this is a research paper, not a textbook) * wonder whether the use of embeddings into the plane can be dispensed with (very roughly, this is like the many examples of proving number theoretic results by using complex analysis); a purely combinatorial proof seems desirable * wonder whether expositions of Power's proof have been given (in particular in textbooks) Currently it seems to me that there is no alternative to simply thoroughly analyzing Power's proof, which I hope I will get round to doing soon.

   Re #2. Thanks for pointing out, I was referring to the planar pasting schemes which are connected by the triple-arrows.
   The “role” of planarity remains not clear (to me). I am aware that the skeleton associahedron (apparently) ceases to be a planar from from $n=6$ onwards.

   Naively, isn’t it natural to

   • expect Power in his article to proactively comment on the role of planarity; his exposition is, roughly, “Bénabou introduced (something formalizable by) planar pasting schemes, and here is a proof that his concept is consistent/coherent.” (Perhaps Power was assuming readers to be well-versed in the combinatorial attempts that he is hinting at in his introduction, Johnson etc.—I recognized this is a research paper, not a textbook)
   • wonder whether the use of embeddings into the plane can be dispensed with (very roughly, this is like the many examples of proving number theoretic results by using complex analysis); a purely combinatorial proof seems desirable
   • wonder whether expositions of Power’s proof have been given (in particular in textbooks)

   Currently it seems to me that there is no alternative to simply thoroughly analyzing Power’s proof, which I hope I will get round to doing soon.

4. • CommentRowNumber4.
   • CommentAuthorTodd_Trimble
   • CommentTimeJul 18th 2017
   • (edited Jul 18th 2017)
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItexNot sure I'm following #1 either. In particular, what is meant by the underlying graph of a "scheme". There are various modes of presentation of higher categorical structure: parity complexes, pasting diagrams, pasting schemes, directed complexes, ... and I suppose Peter is keeping his options open by referring to any one of these as some notion of "scheme". (There is also a notion of computad, which for now I'll skip over. Oh, and of course string diagrams and higher-dimensional analogues of those.) It's been a very long time since I've looked over these four flavors of scheme -- I couldn't tell you the precise axioms for any one of them. But if "parity complex" is somewhat representative, then what is going on in terms of the data is this: * We have sets $C_n$, $n \geq 0$, whose elements are called $n$-cells. * We have relations $\partial_n^-, \partial_n^+: C_{n+1} \rightrightarrows P C_n$ where $\sigma \in \partial_n^\epsilon(\tau)$ is thought of as saying that the $n$-cell $\sigma$ sits on the boundary of the $(n+1)$-cell $\tau$, either on the "negative" or "positive" side of the boundary depending on the sign $\epsilon$. Intuitively I picture each $n$-cell $c$ as a polytope, i.e., an $n$-dimensional compact convex body obtained as an intersection of finitely many half-spaces of an affine space $\mathbb{R}^n$. (I think that of the four flavors, Richard Steiner's directed complexes come closest to capturing this Euclidean-geometric intuition, but I can't promise my memory is accurate.) But evidently these are "oriented" polytopes, with the intuitive sense that a cell $c$ is "moving" (or pushing, or deforming) its negative boundary to its positive one. Again, in this picture, if $c$ is a topological $n$-disk, then the cells of $\partial^-(c)$ fill out say the southern hemisphere of its boundary, and those of $\partial^+(c)$ the northern hemisphere. But then the orientations of the negative cells also move in a consistent direction, collectively pushing one half of the equator (a negative half) toward the other positive half, and so do the oriented positive cells. The "globularity axioms" of parity complexes spell out precisely what is meant by this. In my tetracategory diagrams, each triple arrow that transitions from one page to the next is supposed to be conceived as a local $3$-cell in a hom-tricategory, and is pictured as a 3-dimensional polytope. Or somewhat more accurately: for each transition here's a smallish part that is actually being moved or deformed, a bubble if you like, surrounded by a larger mass which doesn't move during the transition. What is going on here is that in each case we have a higher-dimensional whiskering. If you print those pages out and arrange them in proper order, you should be able to visualize those 3d bubbles more clearly.

   Not sure I’m following #1 either. In particular, what is meant by the underlying graph of a “scheme”.

   There are various modes of presentation of higher categorical structure: parity complexes, pasting diagrams, pasting schemes, directed complexes, … and I suppose Peter is keeping his options open by referring to any one of these as some notion of “scheme”. (There is also a notion of computad, which for now I’ll skip over. Oh, and of course string diagrams and higher-dimensional analogues of those.)

   It’s been a very long time since I’ve looked over these four flavors of scheme – I couldn’t tell you the precise axioms for any one of them. But if “parity complex” is somewhat representative, then what is going on in terms of the data is this:

   • We have sets $C_n$, $n \geq 0$, whose elements are called $n$-cells.

   • We have relations $\partial_n^-, \partial_n^+: C_{n+1} \rightrightarrows P C_n$ where $\sigma \in \partial_n^\epsilon(\tau)$ is thought of as saying that the $n$-cell $\sigma$ sits on the boundary of the $(n+1)$-cell $\tau$, either on the “negative” or “positive” side of the boundary depending on the sign $\epsilon$.

   Intuitively I picture each $n$-cell $c$ as a polytope, i.e., an $n$-dimensional compact convex body obtained as an intersection of finitely many half-spaces of an affine space $\mathbb{R}^n$. (I think that of the four flavors, Richard Steiner’s directed complexes come closest to capturing this Euclidean-geometric intuition, but I can’t promise my memory is accurate.) But evidently these are “oriented” polytopes, with the intuitive sense that a cell $c$ is “moving” (or pushing, or deforming) its negative boundary to its positive one. Again, in this picture, if $c$ is a topological $n$-disk, then the cells of $\partial^-(c)$ fill out say the southern hemisphere of its boundary, and those of $\partial^+(c)$ the northern hemisphere. But then the orientations of the negative cells also move in a consistent direction, collectively pushing one half of the equator (a negative half) toward the other positive half, and so do the oriented positive cells. The “globularity axioms” of parity complexes spell out precisely what is meant by this.

   In my tetracategory diagrams, each triple arrow that transitions from one page to the next is supposed to be conceived as a local $3$-cell in a hom-tricategory, and is pictured as a 3-dimensional polytope. Or somewhat more accurately: for each transition here’s a smallish part that is actually being moved or deformed, a bubble if you like, surrounded by a larger mass which doesn’t move during the transition. What is going on here is that in each case we have a higher-dimensional whiskering. If you print those pages out and arrange them in proper order, you should be able to visualize those 3d bubbles more clearly.

5. • CommentRowNumber5.
   • CommentAuthorMike Shulman
   • CommentTimeJul 18th 2017
   • PermaLink
   Author: Mike Shulman
   Format: MarkdownItexI'm not sure this is relevant, but any pasting composite can be written as a lower dimensional pasting composite by "slicing". For instance, a 3-cell pasting in a 3-category $K$ can also be written as; * a 1-dimensional (linear) composite in a double-hom 1-category $K(A,B)(f,g)$, whose objects are 2-cells in $K$ and whose morphism are 3-cells in $K$, and also * a 2-dimensional pasting composite in a hom-2-category $K(A,B)$, whose objects are 1-cells in $K$, whose morphisms are 2-cells in $K$, and whose 2-cells are 3-cells in $K$. This representation displays less of the geometric structure of a pasting, but on the other hand it makes it simpler and easier to draw. In particular, of course, a 2-dimensional pasting diagram can be drawn on a 2-dimensional piece of paper, whereas a 3-dimensional one can't (other than in projection). This may explain why you see so many 2-dimensional pasting diagrams even in papers about 3-categories: they are the highest dimension (retaining the most geometric structure) that fit on a 2-dimensional piece of paper (or screen).

   I’m not sure this is relevant, but any pasting composite can be written as a lower dimensional pasting composite by “slicing”. For instance, a 3-cell pasting in a 3-category $K$ can also be written as;

   • a 1-dimensional (linear) composite in a double-hom 1-category $K(A,B)(f,g)$, whose objects are 2-cells in $K$ and whose morphism are 3-cells in $K$, and also
   • a 2-dimensional pasting composite in a hom-2-category $K(A,B)$, whose objects are 1-cells in $K$, whose morphisms are 2-cells in $K$, and whose 2-cells are 3-cells in $K$.

   This representation displays less of the geometric structure of a pasting, but on the other hand it makes it simpler and easier to draw. In particular, of course, a 2-dimensional pasting diagram can be drawn on a 2-dimensional piece of paper, whereas a 3-dimensional one can’t (other than in projection). This may explain why you see so many 2-dimensional pasting diagrams even in papers about 3-categories: they are the highest dimension (retaining the most geometric structure) that fit on a 2-dimensional piece of paper (or screen).

6. • CommentRowNumber6.
   • CommentAuthorTodd_Trimble
   • CommentTimeJul 19th 2017
   • (edited Jul 19th 2017)
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItexThis reminds me too of something I learned from Street, that there is a way of defining a strict $\omega$-category as a [[globular set]] $C$ equipped with appropriate operations $$\circ^n_j: C_n \times_{C_j} C_n \to C_n, \qquad \iota^n_j: C_j \to C_n$$ whenever $j \lt n$, such that whenever $j \lt k \lt n$, the $2$-globular set $(C_j, C_k, C_n)$ together with the $\circ$'s and $\iota$'s with these indices $j, k, n$ form a $2$-category.

   This reminds me too of something I learned from Street, that there is a way of defining a strict $\omega$-category as a globular set $C$ equipped with appropriate operations

   $$\circ^n_j: C_n \times_{C_j} C_n \to C_n, \qquad \iota^n_j: C_j \to C_n$$

   whenever $j \lt n$, such that whenever $j \lt k \lt n$, the $2$-globular set $(C_j, C_k, C_n)$ together with the $\circ$’s and $\iota$’s with these indices $j, k, n$ form a $2$-category.

7. • CommentRowNumber7.
   • CommentAuthorPeter Heinig
   • CommentTimeJul 19th 2017
   • (edited Jul 22nd 2017)
   • PermaLink
   Author: Peter Heinig
   Format: MarkdownItexMany thanks for your comments. So far, my understanding of "how essential" planarity is to all of this has not improved, only my understanding of some technicalities. But I am working on it, and have decided to write an exposition, and possibly extensions, of JAlg129, this being such a nice little island of genuine common ground between category theory and graph theory. I should hopefully soon be able to say more. For the time being, allow me to reiterate the implicit reference request from # 3: * do you know of expositions of JAlg129 ? (I would expect such a fundamental-yet-relatively-easy-result to have found its way at least into several, possibly unpublished ecture notes...) * do you know what Power means precisely by (JAlg129, p. 440) > However, the restriction of that [he refers to the thesis of Michael Johnson] work to 2-categories does not yield a theorem and proof with the flavour of that adumbrated in [5] [here Power refers to Kelly--Street LNM 420]. * do you know whether the thesis of Johnson is available? I have not yet looked into what University of Sydney offers in the way of making pre-electronic-times-theses available, but probably will, yet there may be easier ways. EDIT: another go at making a literature-search resulted in: M. Johnson thankfully makes it available himself, [here](http://comp.mq.edu.au/~mike/pubclas.html). This seems to be one of the rather rare cases of someone (me) *under*estimating the onset of the electronic age (of mathematical publishing, I mean). My question for whether there are expositions of Power's theorem remains. I have Johnson's JPAA 62 article before me (which is likely to be partly a publication of his thesis---while he does not make one of those formal this-was-a-thesis-statements), but actually studying JPAA62 and comparing it with Johnson's solution will have to wait. Superficially put, at the risk of missing the point, Johnson is effectively saying in his introduction that there was no proof of the pasting theorem simply because there was no *definition* of a pasting, while Power is effectively saying that many definitions had been tried without satisfactory results, and his is the first successful resolution of the problem. Like I said, I am surely missing something essential still, and hope to soon understand this more deeply.

   Many thanks for your comments.

   So far, my understanding of “how essential” planarity is to all of this has not improved, only my understanding of some technicalities.

   But I am working on it, and have decided to write an exposition, and possibly extensions, of JAlg129, this being such a nice little island of genuine common ground between category theory and graph theory. I should hopefully soon be able to say more.

   For the time being, allow me to reiterate the implicit reference request from # 3:

   • do you know of expositions of JAlg129 ? (I would expect such a fundamental-yet-relatively-easy-result to have found its way at least into several, possibly unpublished ecture notes…)

   • do you know what Power means precisely by (JAlg129, p. 440)

   However, the restriction of that [he refers to the thesis of Michael Johnson] work to 2-categories does not yield a theorem and proof with the flavour of that adumbrated in [5] [here Power refers to Kelly–Street LNM 420].

   • do you know whether the thesis of Johnson is available? I have not yet looked into what University of Sydney offers in the way of making pre-electronic-times-theses available, but probably will, yet there may be easier ways. EDIT: another go at making a literature-search resulted in: M. Johnson thankfully makes it available himself, here. This seems to be one of the rather rare cases of someone (me) underestimating the onset of the electronic age (of mathematical publishing, I mean). My question for whether there are expositions of Power’s theorem remains.

   I have Johnson’s JPAA 62 article before me (which is likely to be partly a publication of his thesis—while he does not make one of those formal this-was-a-thesis-statements), but actually studying JPAA62 and comparing it with Johnson’s solution will have to wait.

   Superficially put, at the risk of missing the point, Johnson is effectively saying in his introduction that there was no proof of the pasting theorem simply because there was no definition of a pasting, while Power is effectively saying that many definitions had been tried without satisfactory results, and his is the first successful resolution of the problem.

   Like I said, I am surely missing something essential still, and hope to soon understand this more deeply.