Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: Polytopal sets?

Evan Patterson (Jul 31 2020 at 22:03):

A simplicial complex is to a simplicial set as a polytopal/polyhedral complex is to a...?

I gather that opetopes and opetopic sets might be part of the answer, but I don't know much about those yet. For now, I'm just looking for general pointers and keywords.

Paolo Capriotti (Aug 01 2020 at 08:45):

Maybe presheaves over a category of abstract polytopes?

Jules Hedges (Aug 01 2020 at 09:03):

Not-an-answer: I thought about 2-dimensional ones of these, which I mentally called "polygonal sets", in the context of string diagrams in computers

Amar Hadzihasanovic (Aug 01 2020 at 09:16):

There is no single generalisation of course, but you may want to take a look at my paper from two days ago...

Amar Hadzihasanovic (Aug 01 2020 at 09:20):

I would say it answers your question for a specific direction of generalisation:

• we see simplices as oriented simplices à la Street, that is, we care about their “globular” orientation as shapes of higher-categorical cells;
• we interpret “polytopes” as spherical abstract polytopes, aka general polytopal tilings of spheres. These are more general than the polytopes considered in your link because those must be convex, but less general than the most general abstract polytopes which can be non-spherical.

Amar Hadzihasanovic (Aug 01 2020 at 09:25):

Opetopes are also a kind of “oriented polytope”, but

• oriented simplices are not in general opetopes, and
• opetopic sets as usually defined only have face operations, that is, they are like semi-simplicial sets, not like simplicial sets.

Evan Patterson (Aug 01 2020 at 18:16):

Thanks everyone, that's helpful.

John Baez (Aug 04 2020 at 00:58):

I don't think opetopes are especially relevant to the original question: they're just a special kind of polytope, so opetopic sets are a bit like simplicial sets or cubical sets or multisimplicial sets: a special kind of "polytopal set" that's good for some purposes and not others.

John Baez (Aug 04 2020 at 01:00):

I wrote down a general definition of 2d polytopal set, or maybe one should say "polygonal set", back when I was studying gadgets called "spin foams". These polygonal sets were presheaves on a category that included a point, an edge, and an $n$-gon for each $n$.

John Baez (Aug 04 2020 at 01:01):

However, I decided nobody would want to read about that, so I instead used a category of 2-dimensional "PLCW complexes", short for "piecewise-linear CW complexes".

John Baez (Aug 04 2020 at 01:02):

People have put a lot of time into studying PLCW complexes of any dimension, so if you're a practical-minded person you can use these to work with "n-dimensional polytopal sets".

John Baez (Aug 04 2020 at 01:02):

However if you're a category theorist you may not like them, since they're defined in a very geometrical way, not as a presheaf category!

John Baez (Aug 04 2020 at 01:07):

In case anyone cares, these are two standard references:

• J. Hudson, Piecewise Linear Topology, W. A. Benjamin, Reading, Massachusetts, 1969.

• C. Rourke and B. Sanderson, Introduction to Piecewise-Linear Topology, Springer, Berlin, 1972.

John Baez (Aug 04 2020 at 01:08):

You may not care about this stuff, but I think the vast amount of work people have done on piecewise-linear topology tends to make people uninterested in developing a more purely combinatorial/category-theoretic approach to "polytopal sets".

Evan Patterson (Aug 04 2020 at 02:08):

Thanks John, it's helpful to have that context. I didn't know about all the work on piecewise-linear complexes.

I should explain why I'm interested in a combinatorial/category-theoretic approach. I'd like to understand how a generalized algebraic theory, like the theory of categories or the theory of double categories, gives rise to a category of presheaves. Like a believing category theorist, I prefer to think that syntactical things like logical theories are just the surface manifestations of algebraic and combinatorial structures. I also have a practical motivation: I want to understand how to effectively represent and manipulate such theories and their models on a computer, as data.

For the theory of categories, you get the familiar graph structure from the types for objects and morphisms, and then the composition operation then becomes a 2-simplex, like in the nerve construction, and the identity operation is also "two-dimensional," but of a different shape. In general, I figure that the types and operations of any generalized algebraic theory should define a shape category of some kind, with a meaningful notion of dimension or grading based on the contexts associated with each type and operation.

Maybe this is something that people already understand from the study of higher categories? If so, that would be great! I just don't have a good grasp on that literature.

Nathanael Arkor (Aug 04 2020 at 02:26):

@Evan Patterson: I'd recommend taking a look at the second section of Fiore's Second-Order and Dependently-Sorted Abstract Syntax, which sketches a categorical model for a class of generalised algebraic theories. In particular, the sorts are modelled by simple categories (essentially dependency diagrams), and the models are given in certain presheaf categories.

Nathanael Arkor (Aug 04 2020 at 02:27):

There's also Garner's Combinatorial structure of type dependency, which also looks at presheaf models, but this may be less useful for what you're interested in, because it's not syntactic.

Nathanael Arkor (Aug 04 2020 at 02:32):

I've also spent some time thinking about data structure representations for generalised algebraic theories and similar: I'd be happy to chat to share ideas at some point.

Evan Patterson (Aug 04 2020 at 02:35):

Thanks Nathanael, I'll take a look at those references. This is something that I've wanted to understand for a long time, so we should definitely chat at some point!

Morgan Rogers (he/him) (Aug 04 2020 at 09:54):

Evan Patterson said:

I should explain why I'm interested in a combinatorial/category-theoretic approach. I'd like to understand how a generalized algebraic theory, like the theory of categories or the theory of double categories, gives rise to a category of presheaves.

In what sense is "gives rise to a category of presheaves" meant? As in, why are algebraic theories classified by presheaf toposes? Or how do presheaf toposes arise as models of the theory of categories?

Jules Hedges (Aug 04 2020 at 10:06):

The line of work that had me thinking about this started from the observation that string diagrams in a 2-category [plus some form of the spacial axiom, so you can ignore scalars] look like labelled polygonal cell complexes. This eventually led me to "rotation systems", which are a combinatorial presentation of planar graphs. I suspect this is all very specialised to 2 dimensions though

Jules Hedges (Aug 04 2020 at 10:08):

(Planar graphs are much more restrictive than general 2d cell complexes though, of course)

Morgan Rogers (he/him) (Aug 04 2020 at 10:22):

If you meant the former, you definitely need to check out some (by now classical) categorical logic literature! Caramello's Theories, Sites, Toposes: Relating and Studying Mathematical Theories Through Topos-theoretic 'bridges' goes through this in a systematic way, having some overlap with Johnstone's Elephant, Section D.

The formal language and notation that this area carries might seem somewhat alien, but the constructions are essentially algebraic: an algebraic signature $\Sigma$ generates a syntactic category, and $\Sigma$-structures are a category with finite limits are finite-limit-preserving functors into that category from the syntactic category. An algebraic theory $\mathbb{T}$ over that signature imposes relationships between subobjects in the syntactic category; the models of $\mathbb{T}$ are the $\Sigma$-structures whose functors respect those relationships. When we're looking at models of an algebraic theory in a topos (or more generally a cocomplete category), we can turn the syntactic category into a classifying topos by taking the free cocompletion (presheaves!) and replacing "functors preserving finite limits" with "functors preserving finite limits and arbitrary colimits", aka "inverse images of geometric morphisms", since these are in correspondence with one another. At this point it should be a little clearer how presheaf toposes come in.

Making this geometric by taking the nerve of the syntactic category, the nerve for the theory is obtained from the nerve for the signature by gluing in higher cells, so that a model of the theory is a model of the empty theory into which extra cells can be glued in. I haven't spent any time working out the details of that last sentence (nor is this geometric picture covered in the sources I referenced, despite them presenting "geometric logic" :stuck_out_tongue_wink: ), it just seems like the closest link to your motivation, if I have understood it correctly.

Amar Hadzihasanovic (Aug 04 2020 at 11:11):

Evan Patterson said:

For the theory of categories, you get the familiar graph structure from the types for objects and morphisms, and then the composition operation then becomes a 2-simplex, like in the nerve construction, and the identity operation is also "two-dimensional," but of a different shape. In general, I figure that the types and operations of any generalized algebraic theory should define a shape category of some kind, with a meaningful notion of dimension or grading based on the contexts associated with each type and operation.

The approach in the paper I linked is precisely in this spirit. It starts from a very general combinatorics of shapes, closed under a lot of operations, whose underlying data structure is “finite graded posets” -- like in the theory of abstract polytopes -- together with an orientation which makes sense for composition in a higher category.

But in there you can isolate particular classes of shapes as being closed under certain operations, and consider categories of presheaves on categories of shapes of a certain class. In my case I was interested in doing “diagram rewriting” in as much generality as possible, so my notion of “convenient class” had to be closed under a lot of stuff that you may not be interested in, for example “opposites in any dimension”. But the two examples you made correspond to two of these closure axioms:

• closure under an operation of “forming shapes of units” over a certain shape,
• closure under the join operation, which implies for example that a convenient class contains all simplices.

So the idea is pretty much what you talk about: the possibility of “doing certain operations” or “manipulations” corresponds to the closure of the shape class under certain operations.

Amar Hadzihasanovic (Aug 04 2020 at 11:19):

On the other hand, I have not yet tried to connect any of that to type-theoretic presentations of algebraic theories -- my intuition comes all from diagrams and topology... So the references that Nathanael gave you would probably be a better starting point for that. :)

Evan Patterson (Aug 04 2020 at 21:56):

Jules Hedges said:

The line of work that had me thinking about this started from the observation that string diagrams in a 2-category [plus some form of the spacial axiom, so you can ignore scalars] look like labelled polygonal cell complexes. This eventually led me to "rotation systems", which are a combinatorial presentation of planar graphs. I suspect this is all very specialised to 2 dimensions though

Although it's outside my original motivation, I'd be curious to hear more about what you came up with. I recently discovered, sort of by accident, that people in computational geometry use combinatorial representations of surface subdivisions that are presheafs or nearly so. For example, this paper on "topological models for boundary representation" describes what the author unhelpfully calls "n-dimensional maps" and "n-dimensional generalized maps". The former are presheaves on a certain category (Def 5) and, apart from a condition about fixed points, so are the latter (Def 1). The representations are rather interesting, with only the "half-edges" corresponding to elements and everything else being encoding by maps. They apparently work best in 2D, where there is a theorem relating them to subdivisions of a surface (Thm 1). I wonder how that relates to what you were thinking about?

Reid Barton (Aug 04 2020 at 22:01):

I don't have convenient access to that paper; are they the same as the "hypermaps" from page 4 of http://www.ams.org/notices/200811/tx081101382p.pdf?

Evan Patterson (Aug 04 2020 at 22:10):

At a glance, they are probably not the same but they seem to be related. In particular, the notion of "dart" appears in both definitions. Frustratingly, I can't find a direct link to a PDF, but here are the two definitions. image.png image.png

Evan Patterson (Aug 04 2020 at 22:11):

The definitions make more sense with a picture. Here is an example for the first definition (an "n-G-map" for n=1): image.png

Evan Patterson (Aug 04 2020 at 22:14):

And for n=2: image.png

Evan Patterson (Aug 04 2020 at 22:19):

Actually, I remember where I saw something very similar to these "hypermaps": the cell-tuple representation in this paper by Brisson. See the figure on p. 221.

Jules Hedges (Aug 04 2020 at 22:22):

Evan Patterson said:

Although it's outside my original motivation, I'd be curious to hear more about what you came up with. I recently discovered, sort of by accident, that people in computational geometry use combinatorial representations of surface subdivisions that are presheafs or nearly so. For example, this paper on "topological models for boundary representation" describes what the author unhelpfully calls "n-dimensional maps" and "n-dimensional generalized maps". The former are presheaves on a certain category (Def 5) and, apart from a condition about fixed points, so are the latter (Def 1). The representations are rather interesting, with only the "half-edges" corresponding to elements and everything else being encoding by maps. They apparently work best in 2D, where there is a theorem relating them to subdivisions of a surface (Thm 1). I wonder how that relates to what you were thinking about?

There's not a whole lot to say... this is being worked on by Malin Altmüller, a PhD student in Strathclyde, I saw a talk by her before christmas and realised it was equivalent to the thing I'd been thinking about (up to graph dual), so then I stopped thinking about it because she was way ahead of me. You might be interested in this https://arxiv.org/abs/1908.10660 which is a tech report rather than a "serious" paper, where we realised that the obvious definition of string diagram by recursive subdivision of the plane, which is also equivalent to proof trees in a fragment of linear logic, also pretty much coincides with a kd-trees, a standard data structure in computational geometry

Jules Hedges (Aug 04 2020 at 22:24):

The pictures you just posted look plausibly related to all this

Evan Patterson (Aug 04 2020 at 22:39):

Neat, it's fun to see how all these pieces fit together. Hope to eventually see a paper from Malin too.

Evan Patterson (Aug 04 2020 at 22:40):

@Reid Barton, thanks for the reference. That AMS Notices paper looks really nice.

Evan Patterson (Aug 04 2020 at 23:07):

[Mod] Morgan Rogers said:

In what sense is "gives rise to a category of presheaves" meant? As in, why are algebraic theories classified by presheaf toposes? Or how do presheaf toposes arise as models of the theory of categories?

I didn't actually have any statement as precise as that in mind. I don't know anything about the classifying topos, so I wouldn't have thought to ask this question. Thanks for explaining the connection to topos theory. When I'm feeling brave I'll try to dig into Caramello's book.

Evan Patterson (Aug 04 2020 at 23:22):

Amar Hadzihasanovic said:

So the idea is pretty much what you talk about: the possibility of “doing certain operations” or “manipulations” corresponds to the closure of the shape class under certain operations.

Thanks a lot for unpacking this for me. I got intimidated by your paper because I don't have the background on higher categories and the homotopy hypothesis, but this helps. Your formalism for diagrammatic sets looks quite interesting.

Spencer Breiner (Aug 06 2020 at 16:46):

I have a tangentially related question:

Does anyone know the name for an open subset $U\subseteq X$ that is invariant under the "double negation" operation ${\Big(X\setminus(X\setminus U)^\circ\big)^\circ}$?

Together with conditions on the boundary, this seems like a nice collection of "regions" (e.g., in a map/$\mathbb{R}^2$) that avoids a lot of unintuitive pathologies.

Reid Barton (Aug 06 2020 at 16:56):

This is a regular open set https://ncatlab.org/nlab/show/regular+element

Tobias Fritz (Aug 06 2020 at 17:01):

Regular opens are indeed considered a lot by philosophers in the context of mereology (the study of regions and parts and wholes). Perhaps this paper may be a good entry point into that literature, but I'm not sure.

Peter Arndt (Aug 06 2020 at 17:17):

There is really nice unpublished work by Marra and Menni on toposes of sheaves on polyhedra. Here are some slides: https://math.unice.fr/tacl/assets/2019/contributed/s3/4/4-marra-menni.pdf

Evan Patterson (Aug 06 2020 at 23:30):

Those slides are indeed really nice. Based on Marra's website, you seem to be right that they have not written it up. I hope they do!