<span class="w"><font size="-2"><span style="font-weight: bold;"><span style="font-weight: bold;"><span style="font-weight: bold;">"Formalized Proof, Computation, and the Construction Problem in Algebraic geometry", by Carlos Simpson.

</span><br>

<br>

</span>[PDF]</b></font></span> 

<h2 class="r"><a class="l" href="http://arxiv.org/pdf/math/0410224">arXiv:<b>math</b>.AG/0410224 v1 8 Oct 2004</a></h2>

<font size="-1"><font color="#6f6f6f">File Format:</font> PDF/Adobe Acrobat - <a href="http://72.14.253.104/search?q=cache:8FWyl8lGqRwJ:arxiv.org/pdf/math/0410224+%22how+many+categories%22+math+theory&hl=en&gl=us&ct=clnk&cd=5">

View as HTML</a><br>finite integer N, <b>how many categories</b> are there with N morphisms? What <b>...</b> Algebraic <b>theory</b> of machines, I. Trans. Amer. <b>Math</b>. Soc. 116 (1965), 450-464.<br>

<br>

<br>

</font><br><div><span class="gmail_quote">On 11/23/06, <b class="gmail_sendername">Jonathan Post</b> <<a href="mailto:jvospost3@gmail.com">jvospost3@gmail.com</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

Roland Bacher correctly refers to quivers as summarized in wikipedia at<br>

<br>

<a href="http://en.wikipedia.org/wiki/Quiver_%28mathematics%29" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://en.wikipedia.org/wiki/Quiver_%28mathematics%29</a><div><span class="e" id="q_10f15cff61fdf42d_1">

<br><br><div><span class="gmail_quote">On 11/22/06, <b class="gmail_sendername">Roland Bacher</b> <

<a href="mailto:Roland.Bacher@ujf-grenoble.fr" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">Roland.Bacher@ujf-grenoble.fr</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

<br>This numbers can also be obtained as the numbers<br>of the following quotients of quivers:<br><br>Associate to a category with n morphisms and k objects<br>the quiver with k vertices corresponding to the objects<br>and a(X,Y) arrows directed from the object X to the object

<br>Y if there are a(X,Y) morphisms from X into Y.<br><br>Given two morphism g:X-->Y, f:Y-->Z with composition<br>h=f o g:X-->Z, put the relation gf=h on the quiver algebra<br><br>The resulting quotient algebra has dimension n and a basis

<br>given by the (simple) arrows.<br><br>This leads to the following "algorithm" for enumerating<br>all categories with n morphisms and k objects:<br><br>(a) enumerate all quivers (directed graphs) with k vertices and

<br>n oriented edges.<br><br>(b) Associate the following "weight" to such a quiver as follows :<br><br>(b1)given a triplet of vertices X,Y,Z,<br>set w(X,Y,Z)=(a(X,Z))^{a(X,Y) \cdot a(Y,Z)}<br>(this counts the number of ways which associate a morphism

X-->Z to a composition X-->Y-->Z) where a(U,V) denotes the number of oriented arrows starting at U and ending at W. (b2) associate to a given quiver the weight \prod_{X,Y,Z} w(X,Y,Z) where the product is over all triplets of vertices.

<br><br>The total sum of such weighted quivers yields then the solution.<br><br>Roland Bacher<br><br><br><br><br><br><br>On Wed, Nov 22, 2006 at 04:20:32PM -0500, <a href="mailto:franktaw@netscape.net" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">

franktaw@netscape.net

</a> wrote:<br>> How many categories are there?<br>><br>> First, how many categories are there with n morphisms and k objects?<br>> This table starts:<br>><br>> 1<br>> 2  1<br>> 7  3 1<br>> 35 16 3 1

<br>><br>> The first column is A058129, the number of monoids; the main diagonal<br>> is all 1's.  I am not<br>> 100% certain of the 16 in the final row.<br>><br>> Taking the row sums, we get:<br>><br>

> 1,3,11,55<br>><br>> the number of categories with n morphisms.  This is probably not in the<br>> OEIS (only<br>> A001776 is possible - other matches become less than A058129).  The<br>> inverse Euler<br>

> transform,<br>><br>> 1,2,8,41<br>><br>> is the number of connected categories with n morphisms; this is<br>> likewise probably not<br>> in the OEIS (only A052447 is possible).<br>><br>> Can somebody generate more data?

<br>><br>> Franklin T. Adams-Watters<br>><br>> A category is a collection of objects and morphisms; each morphism is<br>> from one object<br>> to another (not necessarily different) object.  Where the destination

<br>> of one morphism<br>> is the source of a second, their composition is defined; composition is<br>> associative where<br>> it is defined.  Each object has an identity morphism, which connects it<br>> to itself; this

<br>> is an identity when composed with morphisms coming in and with<br>> morphisms going<br>> out.<br>> ________________________________________________________________________<br>> Check Out the new free AIM(R) Mail -- 2 GB of storage and

<br>> industry-leading spam and email virus protection.<br>><br></blockquote></div><br>

</span></div></blockquote></div><br>