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.
The number of categories for which the number of objects equals the number of morphisms is stable beginning at the category with 0 objects and 0 morphisms. The number is 1.
The number of categories for which there is one more morphism than object is stable beginning at categories with 2 objects and 3 morphisms. The number is 3.
The number of categories for which there are two more morphisms than objects is stable beginning at categories with 4 objects and 6 morphisms. The number is 21.
Using the number of objects and the number of morphisms as coordinates, the sequence at which the number of possible categories becomes stable is .
What are some good questions I should ask about this observation.
Could you maybe elaborate a bit on what you mean by "is stable"? I don't think I'm following what you're saying, currently. (It's also unclear to me how you obtained the numbers 1, 3 and 21.)
If I have a category with objects and morphisms, that means I have one non-trivial morphism. I can place it anywhere, without fear of inconsistent composition data. So, as an endomorphism on each object gives possibilities, all involutions. When you have choices for the , and choices for the . This gives possibilities in total.
Now the next case, I have exactly two extra morphisms beyond the identities. If is endo, no restrictions on are placed; . If is not endo, then either the domains and codomains are disjoint or connected. If they are disjoint, by the above reasoning we have possibilities for placing . If they are not disjoint, then we must have because there is no third morphism to complete a triangle, so I believe there are four possibilities in this case.
So, in total that gives us . One might continue this way, and try to derive a recurrence relation for . It's fun combinatorics, though the heart of it isn't really category theory. (Being more categorical actually suggests a solution: count projective faithful and injective unfaithful functors that map commuting diagrams to diagrams with one fewer distinct morphism or object, and here labels do matter as we don't see the whole category. This is of more direct categorical interest, and I think can be recovered from this using mobius-inversion followed by some kind of trace?)
Certainly combinatorics isn't irrelevant to category theory, there's a book by Amar Hadzihasanovic on how to use colored hasse diagrams and posets of simplicial complexes and etc. etc. to do diagram rewriting in n-catgeories.
Ah! this is the book I was thinking of! Amar Hadzihasanovic' book *Combinatorics of higher-categorical diagrams*, an advanced topic, but the first chapter is accessible to anyone and its got beautiful diagrams.
I don't know if anyone has worked out the simpler combinatorics of . It might turn into a fun exercise in generating functions.
It's worth noting that other complications start to creep in with a larger number of morphisms.
Like, above, we don't have to worry about different ways composition data can satisfy. In the case we could have or , but upon deeper reflection those are saying exactly the same thing; the cyclic group of order 3.
But, with say , we can have distinct , so for instance we might have or we could have
.
In a Yoneda sense (possibly more congruencies) in the latter case. But if labels matter (that is, there is secret information that only the labeler knows, not represented in the category) then they can remain distinct.
This is catgeory theory, so lets say that the Yoneda lemma always takes precedence, and so that last case was actually . So then: can you find a finite category where the same labelled distinct arrows have at least two possible sets of non-isomorphic composition data? That seems like a fun exercise for the combinatorial-minded and is on-topic.
(⨾ reads "and then" as opposed to "before")
I think I understand what Julius is doing.
A project
that enumerated these used the implicit concept of a category algebra to count finite cats. That is they took a functor from the category to a monoid, looked at the cayley table of said monoid, and adjoined a zero morphism for when . Then they use lexicographic sorting on the cayley tables to deal with the isomorphic copies.
If you look at the table on slide 3, you will see the numbers Julius is referring to. The "stability" appears to be that the number for objects, morphisms might not change as you hold constant and increase . This is borne out by a query to smallcats; sure enough yields 21.
I want to emphasize several things though @Julius Hamilton
That said, while the brute force approach is not really available, there might well be asymptotic methods that will yield the shape of which seems to be what you're looking for.
Eric M Downes said:
I'm not able to find a combination that gives 3, so I am also unsure what Julius is doing there.
I think you missed the case where the extra arrow is idempotent.
Spencer Breiner said:
Eric M Downes said:
I'm not able to find a combination that gives 3, so I am also unsure what Julius is doing there.
I think you missed the case where the extra arrow is idempotent.
Hmmm... I don't think so? For (that is, 3 arrows, 2 objects) I have this
(the top cases involve idempotent arrows; so 4 graphs, and 2 isomorphism classes.)
Cruttwell agrees with you, though @Spencer Breiner so I must be missing something obvious! :)
Ah ok, the two discrete categories are isomorphic as graphs but not functorially. Duh.
Because of course we want our isomorphisms to be in :) So the correct picture is this
So, yeah we really do want to be thinking and computing in terms of images of commuting diagrams.
Nevermind, I'm still confused. This is an isomorphism (and not an automorphism) in . Let be the discrete category of two objects having an involution and be discrete, 2-objs, with an involution .
and
exhibits an isomorphism, yes?
Okay I have either had not enough, or too much coffee, so I'll stop spamming y'all until I can do math again.
Probably clearer to use and , with and but I still claim that pair of functors is an isomorphism in and not 3 as one finds in the tables and on smallcats.
It's not an issue of involutions. You've missed the idempotent. Forget about the second object for a moment. The key issue is that, although there is only one group with two elements, there are two monoids with two elements. In one the non-identity element satisfies (that's the group), but in the other we have .
Perfect, thanks.
These 2-element monoids are sometimes known as "booleans with inclusive or as the binary operation" and "booleans with exclusive or as the binary operation".
Back to Julius' original question: when calculating (num cats with morphisms and objects) why do some values seem to quickly stabilize as , and does it mean anything?
If you expand as a sum over unlabelled graphs, like this
you can separate out the shapes of the graphs somewhat from the combinatorics of valid composition data. Once you have set a graph, the number of categories it contributes, while possibly quite large, doesn't change as you increase the number of morphisms or objects elsewhere.
You can also see that certain graphs with high morphisms-per-object weigh much more heavily in the totals. You can see this intuitively, even if you have, say, forgotten that idempotents exist. :)
Just observe that the number of monoids grows quite fast indeed with the number of arrows. In contrast by inspection, adding a morphism to a previously disjoint object gets you many fewer new categories, then by adding an endomorphism. In fact, the worst case, giving you the fewest new categories per morphism, is to build a long composition chain. Every previously-disjoint object you connect costs a small triangular number of chain-lengths that you must pay to the Federal Composition Enforcement Agency; tax = 0, 1, 3, 6, 10,...
So, when you hold constant but increase , you are "spreading" the morphisms over more and more objects, and eventually there are no more novel graphs to be gained as new objects appear. So the numbers stop increasing and "stabilize" at the constant amounts contributed by each unlabelled graph.
I think you could make this more precise and estimate how large needs to be to ensure . I think it would involve some fun combinatorics and asymptotic methods, but have few immediate categorical insights... most categories, at least that I encounter, have no shortage of morphisms! If you think about universal properties, they're always defined in terms of "for every such and such, Universal X behaves so-and-so"; there are often many such-and-suchs. (If you have a class of locally-finite categories in mind, and a trace is involved, it might be useful?)
So, perhaps the big picture takeaway here** is that we actually have to learn to reliably manipulate category theorems because the combinatorics are so explosive against us.
** -- Also that "idempotent" and "involution", while both 4-syllable words that start with "i" are apparently different words! Shocking, right?! (Thanks, Spencer)