Categories

[Jonathan Post]

I strongly agree with Christian.  My doctoral dissertation involved taking
the Krohn-Rhodes decomposition of the semigroup of differential operators of
a system of nonlinear differential equations that had been in the
mathematical Biology literature for decades, and routinely dismissed as not
capable of closed-form solution. Marvin Minsky (who had been the PhD advisor
of the eponymous John Rhodes) thought my work was the best use yet of his
student's theorem.  The great Stan Ulam (coinventor of cellular automata,
the H-bomb, and the nuclear pulse rocket) also thought it was cool. But only
half a dozen biologists in theb world knew that much about semigroups, and
some of them wrote to me from Edinburgh, Scotland, and places in the USSR.
Ulam died before we could coauthor; Semigroup Forum accepted my paper with
delight for a special issue, but wanted it reformatted, and I was laid off
from the company where I worked, and they erased on only machine-readable
version of the paper.  Equations were harder to typeset those decades
ago...  But yes, lots of so-called professionals go out of their way to
avoid citing the OEIS, or give any useful examples.  Also yes: semigroup
enumerations are worthwhile.  Also, you nailed the differences between those
and categories.

See for instance:

  A118581 <http://www.research.att.com/~njas/sequences/A118581> Number of
nonisomorphic *semigroups* of order <= n.

  A118099 <http://www.research.att.com/~njas/sequences/A118099> Number of
inverse *semigroups* of order <= n.

  A118100 <http://www.research.att.com/~njas/sequences/A118100>

Number of commutative *semigroups* of order <= n.

  A118601 <http://www.research.att.com/~njas/sequences/A118601> Number of
monoids (*semigroups* with identity) of order <= n.
  A113534 <http://www.research.att.com/~njas/sequences/A113534> Ascending
descending base exponent transform of the flipped tribonacci substitution (
A092782 <http://www.research.att.com/~njas/sequences/A092782>).
with its semigroup reference, and some others.

-- Jonathan


On 11/30/06, Christian G. Bower <bowerc at usa.net> wrote:
>
>
>
> ------ Original Message ------
> Received: Thu, 30 Nov 2006 10:34:55 AM PST
> From: "Jonathan Post" <jvospost3 at gmail.com>
> To: "franktaw at netscape.net" <franktaw at netscape.net>Cc: bowerc at usa.net,
> seqfan at ext.jussieu.fr, jvospost2 at yahoo.com
> Subject: Re: Categories
>
> > a(n) = 2*A000055(n) - A000081(n/2) = (2* Number of trees with n
> unlabeled
> > nodes) - Number of rooted trees with n/2 nodes (or connected functions
> with
> > a fixed point)
> >
> > where a(n) is downwards sloping diagonal sums of main category table, or
> > what?
>
> Actually it's the "corner" values from this table
>
> >   *1*
> >   2
> >   7 *1*
> >  35 6
> > 228 28 *2*
> > 2237 159 11
> > 31559 ?   ? *3*
>
> The downward sloping sums were an aide in calculating the convergent
> sequence of the columns
>
> The interpretation of these corners comes from the fact we have a
> saturated category. It has 2n-1 elements, n of which are object
> identities. It's connected, so it has a minimum of n-1 "crossover"
> morphisms, it also has a maximum of n-1 cm's since there are only
> n-1 elements left. Any connected graph with n points and n-1 edges is
> a tree. The associativity of categories states that if we have an
> a-b morphism (an edge on the graph) and a b-c we must have an a-c.
> But if we have all 3, it's no longer a tree, hence we never have the
> a-b and the b-c, hence each point has all edges either pointing in or
> pointing out, hence the biparite graph analogy, hence a little
> combinatorial magic.
>
> ...
> > Funny how Category Theory folks tend to be addicted to theory for its >
> own
> > sake, and less willing to "get their hands dirty" with anything as old
> > fashioned as enumeration.  OEIS helps us focus here, by demanding the
> > integer sequences!
> >
>
> I try to stay out of philosophical stuff here, but sometimes it's too
> hard to resist. I figure I'm guilty of spending too much time counting
> stuff and not taking the theory in. Most of the world would not give a
> hoot about either, so I'm glad there are folk spending time on what I
> would not give any time to.
>
> Still, I find it jarring any time I read a math paper and they write
> about several things that can be represented as sequences, yet all they
> give is a mathematical description, rarely do they cite the OEIS
> reference or even give me the first n terms leaving me to calculate them
> myself and hope I didn't make a mistake. If I wrote a paper, I'd
> include that stuff, not just because I'm an OEIS nerd, but also because
> I would want people to be able to find my paper who didn't know they
> were looking for it.
>
> Just a little more self indulgence here with my list of semigroup pipe
> dreams. After doing sequences on semigroups
> http://www.research.att.com/~njas/sequences/A027851
> and monoids
> http://www.research.att.com/~njas/sequences/A058129
> I knew categories was one of the next logical steps, but I held off
> because I knew it would be difficult. Perhaps I can spur someone else's
> interest in related problems that may prove even more difficult.
>
> There's transformation semigroups, the semigroup version of permutation
> groups
> http://www.research.att.com/~njas/sequences/A000638
> I've seen TSs written about, but no attempts to enumerate them.
> (Note, a TS is any set of endofunctions closed under composition)
> There TS's close cousins which could be called:
> transformation monoids
> relation semigroups
> relation monoids
> (Composition of relations is such that (a,c) is in R1(R2) iff there
> is b such that (a,b) in R1 and (b,c) in R2)
> Then there are the generalizations of categories to semigroups and
> groupoids. Note I mean the groupoid that is a set and closed operation
> http://www.research.att.com/~njas/sequences/A001329
> Not the group like category groupoid which might also be interesting
> to count and not too difficult; oh terminology.
> Anyway, with the semigroup and groupoid categories, there comes the
> issue of treating objects and morphims. The ordinary (monoid like)
> categories avoid this problem by having object identities among the
> morphisms that can be associatied with the objects themselves. Without
> that restriction, it's possible to have objects untouched by any
> morphism or two structures with identical (or isomorphic) multiplication
> tables, but not isomorphic when you take the objects into account.
> Basically many of the same counting problems one has with multigraphs
> (and probably the same solutions too.)
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20061130/c67b9e93/attachment-0003.htm>