Categories

Fri Nov 24 23:41:12 CET 2006

Somehow the reply to Frank went astray.

The wikipedia entry on directed graph makes some of the definitional
distinctions I've made, and then some.  Further, it makes the useful
statement:

In Category theory,
a category can be considered a directed multigraph
with the objects as vertices and the morphisms as directed edges.
The functors between categories induce then some,
but not necessarily all, of the digraph morphisms.

-- Jonathan

On 11/24/06, Jonathan Post <jvospost3 at gmail.com> wrote:
>
> Offline, I'm coordinating with Edwin Clark on definitions.
>
> But I'm counting as lower bounds  (many pages of paper with drawings, too
> lengthy for me to turn into ascii, don't have scanner):
>
> 2 categories on 1 point;
> 6 categories on 2 points;
> 16 categories on 3 points;
> 46 categories on 4 points;
> 116 categories on 2 points;
>
> in each case where the underlying digraph is of an endofunction. The full
> count on categories on n points is a weighted partial sum on these, related
> to my enumeration of "prime" endofunctions being the sum of Fobonacci(n),
> tribonacci(n), teranacci(n), ...
>
> -- I can give examples on request.  Of course, I can always be off by 1 or
> more on each count, through sheer blunder.  But I am being self-consistent
> in methodology, and it can be done by software using the same algorithm,
> carefully translated.
>
> -- Jonathan
>
>
> 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/20061124/e521f1cc/attachment-0003.htm>