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


view this post on Zulip 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),(0,0), (2,3), (4,6), (6,9), (8,12),….

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

view this post on Zulip 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.)

view this post on Zulip Eric M Downes (Jun 01 2024 at 06:23):

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

Now the next case, I have exactly two extra morphisms f,gf,g beyond the identities. If ff is endo, no restrictions on gg are placed; n2n^2. If ff is not endo, then either the domains and codomains are disjoint or connected. If they are disjoint, by the above reasoning we have (n2)2(n-2)^2 possibilities for placing gg. If they are not disjoint, then we must have {cod.g,dom.g}{cod.f,dom.f}\{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 cn,n+2=nn2+n(n1)[(n2)2+4]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 co,mc_{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 co,mc_{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.

view this post on Zulip 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 co,mc_{o,m}. It might turn into a fun exercise in generating functions.

view this post on Zulip 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:XXf,g:X\to X we could have f2=g,f3=1Xf^2=g, f^3=1_X or fg=gf=1Xf\circ g=g\circ f=1_X, but upon deeper reflection those are saying exactly the same thing; {f,g,1X}C3\{f,g,1_X\}\cong C_3 the cyclic group of order 3.

But, with say m=4m=4, we can have distinct f,g:XY, h:YX, e:XXf,g:X\to Y,~h:Y\to X, ~e:X\to X, so for instance we might have fh=1X,gh=ef⨾ h=1_X, g⨾ h=e or we could have
fh=e=gh, x,y,dom.x=X,cod.y=X; ex=x,ye=yf⨾ h=e=g⨾ h, ~\forall x,y, dom.x=X, cod.y=X; ~ e⨾ x=x, y⨾e = y.
In a Yoneda sense fgf\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 m3m\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.

view this post on Zulip Eric M Downes (Jun 01 2024 at 07:12):

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

view this post on Zulip 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 coddomcod\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 nn objects, n+Δn+\Delta morphisms might not change as you hold Δ\Delta constant and increase nn. This is borne out by a query to smallcats; n=5,Δ=2n=5, \Delta=2 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 c(Δ)=limncn,n+Δc^\infty(\Delta)=\lim_{n\to\infty}c_{n,n+\Delta} which seems to be what you're looking for.

view this post on Zulip 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.

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

view this post on Zulip Eric M Downes (Jun 01 2024 at 14:00):

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

view this post on Zulip Eric M Downes (Jun 01 2024 at 14:01):

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

view this post on Zulip Eric M Downes (Jun 01 2024 at 14:15):

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

view this post on Zulip Eric M Downes (Jun 01 2024 at 14:18):

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

view this post on Zulip 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.

view this post on Zulip Eric M Downes (Jun 01 2024 at 14:39):

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

F:CC; Fx=x,Fx=x,Fe=eF:{\sf C\to C'}; ~Fx=x', Fx'=x, Fe=e' and
F:CC; Fx=x,Fx=x,Fe=eF':{\sf C'\to C};~F'x=x', F'x'=x, Fe'=e
FF=idC,FF=idCF\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.

view this post on Zulip Eric M Downes (Jun 01 2024 at 14:52):

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

view this post on Zulip 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 mm satisfies mm=idm\circ m = {\rm id} (that's the group), but in the other we have mm=mm\circ m = m.

view this post on Zulip Eric M Downes (Jun 01 2024 at 19:12):

Perfect, thanks.

view this post on Zulip 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".

view this post on Zulip Eric M Downes (Jun 02 2024 at 06:39):

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

If you expand cn,n+Δ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(n1)/2n(n-1)/2 of chain-lengths nn 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Δ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Δn\gg \Delta needs to be to ensure cn,n+Δc(Δ)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)