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: When the number of categories becomes stable

Julius Hamilton (May 31 2024 at 23:25):

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 $(0,0), (2,3), (4,6), (6,9), (8,12),…$.

What are some good questions I should ask about this observation.

David Egolf (Jun 01 2024 at 00:08):

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.)

Eric M Downes (Jun 01 2024 at 06:23):

If I have a category with $n$ objects and $n+1$ 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 $n$ possibilities, all involutions. When $dom.f\neq cod.f$ you have $n$ choices for the $dom$, and $n-1$ choices for the $cod$. This gives $c_{n,n+1}=n^2$ possibilities in total.

Now the next case, I have exactly two extra morphisms $f,g$ beyond the identities. If $f$ is endo, no restrictions on $g$ are placed; $n^2$. If $f$ is not endo, then either the domains and codomains are disjoint or connected. If they are disjoint, by the above reasoning we have $(n-2)^2$ possibilities for placing $g$. If they are not disjoint, then we must have $\{cod.g,dom.g\}\subseteq\{cod.f,dom.f\}$ 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 $c_{n,n+2}=n*n^2+n(n-1)*[(n-2)^2+4]$. One might continue this way, and try to derive a recurrence relation for $c_{o,m}$. 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 $c_{o,m}$ 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.

Eric M Downes (Jun 01 2024 at 06:32):

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 $c_{o,m}$. It might turn into a fun exercise in generating functions.

Eric M Downes (Jun 01 2024 at 07:07):

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 $f,g:X\to X$ we could have $f^2=g, f^3=1_X$ or $f\circ g=g\circ f=1_X$, but upon deeper reflection those are saying exactly the same thing; $\{f,g,1_X\}\cong C_3$ the cyclic group of order 3.

But, with say $m=4$, we can have distinct $f,g:X\to Y,~h:Y\to X, ~e:X\to X$, so for instance we might have $f⨾ h=1_X, g⨾ h=e$ or we could have
$f⨾ h=e=g⨾ h, ~\forall x,y, dom.x=X, cod.y=X; ~ e⨾ x=x, y⨾e = y$.
In a Yoneda sense $f\cong g$ (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 $m\leq3$. 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.

Eric M Downes (Jun 01 2024 at 07:12):

(⨾ reads "and then" as opposed to $\circ$ "before")

Eric M Downes (Jun 01 2024 at 12:38):

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 $cod\neq dom$. 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 $n$ objects, $n+\Delta$ morphisms might not change as you hold $\Delta$ constant and increase $n$. This is borne out by a query to smallcats; $n=5, \Delta=2$ sure enough yields 21.

I want to emphasize several things though @Julius Hamilton

• here I think it will bear out, but in general there are infamous examples in math of seemingly stable sequences that blow up at some random number. Be wary of jumping to conclusions.
• the techniques here are all graph theory, and the reason they didn't get very far is because brute-forcing the graph isomorphism problem sucks very fast; it might be an NP-complete problem.

That said, while the brute force approach is not really available, there might well be asymptotic methods that will yield the shape of $c^\infty(\Delta)=\lim_{n\to\infty}c_{n,n+\Delta}$ which seems to be what you're looking for.

Spencer Breiner (Jun 01 2024 at 13:30):

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.

Eric M Downes (Jun 01 2024 at 13:58):

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 $n=2,\Delta=1$ (that is, 3 arrows, 2 objects) I have this

Eric M Downes (Jun 01 2024 at 14:00):

(the top cases involve idempotent arrows; so 4 graphs, and 2 isomorphism classes.)

Eric M Downes (Jun 01 2024 at 14:01):

Cruttwell agrees with you, though @Spencer Breiner so I must be missing something obvious! :)

Eric M Downes (Jun 01 2024 at 14:15):

Ah ok, the two discrete categories are isomorphic as graphs but not functorially. Duh.

Eric M Downes (Jun 01 2024 at 14:18):

Because of course we want our isomorphisms to be in $\sf Cat$ :) So the correct picture is this

Eric M Downes (Jun 01 2024 at 14:27):

So, yeah we really do want to be thinking and computing in terms of images of commuting diagrams.

Eric M Downes (Jun 01 2024 at 14:39):

Nevermind, I'm still confused. This is an isomorphism (and not an automorphism) in $\sf Cat$. Let $\sf C$ be the discrete category of two objects having an involution $e:X\to X$ and $\sf C'$ be discrete, 2-objs, with an involution $e':X'\to X'$.

$F:{\sf C\to C'}; ~Fx=x', Fx'=x, Fe=e'$ and
$F':{\sf C'\to C};~F'x=x', F'x'=x, Fe'=e$
$F\circ F'=id_{\sf C'}, F'\circ F=id_{\sf C}$

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.

Eric M Downes (Jun 01 2024 at 14:52):

Probably clearer to use $a,b\in{\sf C}$ and $a',b'\in{\sf C'}$, with $F:(a,b,e)\mapsto(b',a',e')$ and $F'(a',b',e')\mapsto(b,a,e)$ but I still claim that pair of functors is an isomorphism in $\sf Cat$ and $c_{2,3}=2$ not 3 as one finds in the tables and on smallcats.

Spencer Breiner (Jun 01 2024 at 17:51):

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 $m$ satisfies $m\circ m = {\rm id}$ (that's the group), but in the other we have $m\circ m = m$.

Eric M Downes (Jun 01 2024 at 19:12):

Perfect, thanks.

John Baez (Jun 01 2024 at 19:15):

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".

Eric M Downes (Jun 02 2024 at 06:39):

Back to Julius' original question: when calculating $c_{n,n+\Delta}$ (num cats with $n+\Delta$ morphisms and $n$ objects) why do some values seem to quickly stabilize as $n\to\infty$, and does it mean anything?

If you expand $c_{n,n+\Delta}$ 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 $n(n-1)/2$ of chain-lengths $n$ that you must pay to the Federal Composition Enforcement Agency; tax = 0, 1, 3, 6, 10,...

So, when you hold $\Delta$ constant but increase $n\gg \Delta$, 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 $n\gg \Delta$ needs to be to ensure $c_{n,n+\Delta}\approx c^\infty(\Delta)$. 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)