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.
Jens Hemelaer (Nov 20 2020 at 14:48):In universal algebra, a category is called universal if it has a full subcategory that is equivalent to the category of directed graphs. While preparing a paper with @[Mod] Morgan Rogers, I read some interesting results about universality in the textbook by Pultr and Trnková: "Combinatorial, algebraic and topological representations of groups, semigroups and categories". I'll post them here, maybe others here will find them interesting as well.
The definition of universality may look a bit strange (why directed graphs?) But it is known that any small category has a full embedding in the category of directed graphs. Even better: any concrete category has a full embedding in the category of directed graphs, under some set-theoretical and class-theoretical assumptions. So a universal category contains almost any category that you can think of, as a full subcategory.
Pultr and Trnková then consider the categories of presheaves for small categories . They call "rich" if is universal.
It turns out that rich categories have at least four morphisms. One of these is the category with two objects and and two maps (so four maps if we count the identities). The presheaf category is then the category of directed graphs, so it is universal by definition.
What about categories with one object (monoids)? It was shown by Jiří Sichler in his thesis that the smallest rich monoids has five elements.
Another family are the "thin categories" (i.e. there is at most one morphism between every two objects). A result by Trnková and Reiterman then states that a thin category is rich if and only if it contains one of the 35 thin categories in the list below, as a full subcategory...
basic-thin.png
Matteo Capucci (he/him) (Nov 20 2020 at 15:33):I need a t-shirt with that image
Matteo Capucci (he/him) (Nov 20 2020 at 15:34):Do you have any handwavy intuition about why exactly those 35 cats?
Matteo Capucci (he/him) (Nov 20 2020 at 15:35):Also k_17 seems to contain k_19?
Matteo Capucci (he/him) (Nov 20 2020 at 15:36):Same with k_14 and k_13
Reid Barton (Nov 20 2020 at 15:38):more useful than my observation: you can make a bacteriophage by gluing k_27 and k_31
Jens Hemelaer (Nov 20 2020 at 15:42):Matteo Capucci said:
Do you have any handwavy intuition about why exactly those 35 cats?
No, and I haven't looked at the proof yet.
Jules Hedges (Nov 20 2020 at 15:44):Wow! :heart_eyes_cat: [brain explodes]
Jens Hemelaer (Nov 20 2020 at 15:44):Matteo Capucci said:
Also k_17 seems to contain k_19?
A thin category is rich if it contains one of the 35 as full subcategory, I forgot to add this in the original post.
Matteo Capucci (he/him) (Nov 20 2020 at 15:56):Ooh, I see
Morgan Rogers (he/him) (Nov 20 2020 at 16:09):Does the final row contain infinite families, or are they just countably infinite posets?
Jens Hemelaer (Nov 20 2020 at 16:39):[Mod] Morgan Rogers said:
Does the final row contain infinite families, or are they just countably infinite posets?
They should be countably infinite posets, but I don't know how to interpret k_34.
Morgan Rogers (he/him) (Nov 20 2020 at 16:41):Yeah, those dots are very mysterious...
Dan Doel (Nov 20 2020 at 16:41):It looks like the main thing is the opposite of with edges out of and into .
Jules Hedges (Nov 20 2020 at 16:45):Somewhere we had a thread about classification theorems in category theory, and this would be a perfect addition there. But I can't find it
Jens Hemelaer (Nov 20 2020 at 19:00):You can download the paper by Trnková and Reiterman here (52 pages).
Another fascinating result from that paper: a thin category is rich if and only if there is an object in that has endomorphism monoid .