[New thread because, although it existed since 2012, pasting scheme appears not to have had a LatestChanges thread]
Started to expand pasting schemes. Intend to do more on this soon, in an integrated fashion with digraph and planar graph.
PLEASE note: ACCIDENTALLY a page pasting schemes was created too, as a result of some arcane issues with pluralized names of pages-still-empty. Please delete pasting schemes.
]]>Created digraph. Some background: this discussion. Created with permission, in the sense of
]]>If you really want to split off material that is pertinent to digraphs in the graph-theorist’s sense, then I myself would have no objection to a new article “digraph”.
[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
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.
]]>Like suggested by someone else in this forum, here I propose creating an article, but will wait for agreement or disagreement before creating it.
The article would be called
category of simple graphs with embeddings
and would
be partly modelled on, and aiming for consistency with, the article category of simple graphs
treat and compare at least three wide subcategories of category of simple graphs, namely
(weak.emb) countable simple graphs with weak graph-embeddings
(strong.emb) countable simple graphs with all strong graph-embeddings
(isom.emb) countable simple graphs with all isometric graph-embeddings
Part of the motivation for this:
Apart from the personal motivation of giving structure to my n-th attempt to get the manuscript into a satisfying form, this comparison would perhaps also be mildy interesting from a pure categorical point of view, since
Part of my motivation for creating left cancellative categories is our interest in category (isom.emb).
Do you agree that such an article could fit into the nlab?
Incidentally, I know that wide subcategories are a concept to which sometimes a certain four-letter-word is applied. Nevertheless, it seems to me that
^{ 1 } Actually, it seems that we can prove something considerably stronger, namely that this class of graphs is not closed under elementary equivalence. (synonyms: the class is not elementarily closed$=$ the class is not $\Sigma\Delta$-elementary) Moreover, what we are mostly interested in is the non-elementarily-closedness (and hence non-elementarity) of various subclasses of the class of all vertex-reconstructible graphs. (Proving that the latter class is not elementarily closed does not need https://arxiv.org/abs/1606.02926) For example, it seems we can prove that the class of all vertex-reconstructible locally-finite forests is not elementarily closed. For proving that, the methods of https://arxiv.org/abs/1606.02926 appear essential.
]]>