Categories

[Jonathan Post]

I can, with Edwin Clark's permission, forward to Frank my complete
correspondance with Edwin Clark about category enumeration via careful
definition.  I am asked not to cut & paste out of context.  But my emails to
Franklin T. Adams-Watters alone went astray, for whatever reason. so I am
not sure what to do.  I've also asked some Haskell programming experts about
Frank's enumeration question (properly citing Frank), as Haskell has monads
and functors and other categorical stuff built in.  I'll share any useful
answers that I get.

On 11/23/06, Roland Bacher <Roland.Bacher at ujf-grenoble.fr> wrote:
>
>
> I realised that the formula below for enumerating categories
> using quivers is completely wrong. It gives only an upper bound
> since one has to require moreover associativity for the composition of
> morphisms. The quiver approach works however in principle but
> is much more complex (and I guess this approach has been
> used in some of the previous approaches).   Roland Bacher
>
> On Thu, Nov 23, 2006 at 12:10:51PM -0800, Jonathan Post wrote:
> > *"Formalized Proof, Computation, and the Construction Problem in
> Algebraic
> > geometry", by Carlos Simpson.
> >
> > [PDF]* arXiv:*math*.AG/0410224 v1 8 Oct
> > 2004<http://arxiv.org/pdf/math/0410224> File
> > Format: PDF/Adobe Acrobat - View as
> > HTML<
> 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
> >
> > finite integer N, *how many categories* are there with N morphisms? What
> *
> > ...* Algebraic *theory* of machines, I. Trans. Amer. *Math*. Soc. 116
> > (1965), 450-464.
> >
> >
> >
> > On 11/23/06, Jonathan Post <jvospost3 at gmail.com> wrote:
> > >
> > >Roland Bacher correctly refers to quivers as summarized in wikipedia at
> > >
> > >http://en.wikipedia.org/wiki/Quiver_%28mathematics%29
> > >
> > >On 11/22/06, Roland Bacher < Roland.Bacher at ujf-grenoble.fr> wrote:
> > >>
> > >>
> > >> This numbers can also be obtained as the numbers
> > >> of the following quotients of quivers:
> > >>
> > >> Associate to a category with n morphisms and k objects
> > >> the quiver with k vertices corresponding to the objects
> > >> and a(X,Y) arrows directed from the object X to the object
> > >> Y if there are a(X,Y) morphisms from X into Y.
> > >>
> > >> Given two morphism g:X-->Y, f:Y-->Z with composition
> > >> h=f o g:X-->Z, put the relation gf=h on the quiver algebra
> > >>
> > >> The resulting quotient algebra has dimension n and a basis
> > >> given by the (simple) arrows.
> > >>
> > >> This leads to the following "algorithm" for enumerating
> > >> all categories with n morphisms and k objects:
> > >>
> > >> (a) enumerate all quivers (directed graphs) with k vertices and
> > >> n oriented edges.
> > >>
> > >> (b) Associate the following "weight" to such a quiver as follows :
> > >>
> > >> (b1)given a triplet of vertices X,Y,Z,
> > >> set w(X,Y,Z)=(a(X,Z))^{a(X,Y) \cdot a(Y,Z)}
> > >> (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.
> > >>
> > >> The total sum of such weighted quivers yields then the solution.
> > >>
> > >> Roland Bacher
> > >>
> > >>
> > >>
> > >>
> > >>
> > >>
> > >> On Wed, Nov 22, 2006 at 04:20:32PM -0500, franktaw at netscape.netwrote:
> > >> > How many categories are there?
> > >> >
> > >> > First, how many categories are there with n morphisms and k
> objects?
> > >> > This table starts:
> > >> >
> > >> > 1
> > >> > 2  1
> > >> > 7  3 1
> > >> > 35 16 3 1
> > >> >
> > >> > The first column is A058129, the number of monoids; the main
> diagonal
> > >> > is all 1's.  I am not
> > >> > 100% certain of the 16 in the final row.
> > >> >
> > >> > Taking the row sums, we get:
> > >> >
> > >> > 1,3,11,55
> > >> >
> > >> > the number of categories with n morphisms.  This is probably not in
> > >> the
> > >> > OEIS (only
> > >> > A001776 is possible - other matches become less than A058129).  The
> > >> > inverse Euler
> > >> > transform,
> > >> >
> > >> > 1,2,8,41
> > >> >
> > >> > is the number of connected categories with n morphisms; this is
> > >> > likewise probably not
> > >> > in the OEIS (only A052447 is possible).
> > >> >
> > >> > Can somebody generate more data?
> > >> >
> > >> > Franklin T. Adams-Watters
> > >> >
> > >> > A category is a collection of objects and morphisms; each morphism
> is
> > >> > from one object
> > >> > to another (not necessarily different) object.  Where the
> destination
> > >> > of one morphism
> > >> > is the source of a second, their composition is defined;
> composition
> > >> is
> > >> > associative where
> > >> > it is defined.  Each object has an identity morphism, which
> connects
> > >> it
> > >> > to itself; this
> > >> > is an identity when composed with morphisms coming in and with
> > >> > morphisms going
> > >> > out.
> > >> >
> > >>
> ________________________________________________________________________
> > >> > Check Out the new free AIM(R) Mail -- 2 GB of storage and
> > >> > industry-leading spam and email virus protection.
> > >> >
> > >>
> > >
> > >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20061126/f987854d/attachment-0003.htm>