Skip to Content »

Michi’s blog » archive for 'Operads and PROPs'

 Species, derivatives of types and Gröbner bases for operads

  • December 18th, 2010
  • 2:05 am

This is a typed up copy of my lecture notes from the combinatorics seminar at KTH, 2010-09-01. This is not a perfect copy of what was said at the seminar, rather a starting point from which the talk grew.

In some points, I’ve tried to fill in the most sketchy and un-articulated points with some simile of what I ended up actually saying.

Combinatorial species started out as a theory to deal with enumerative combinatorics, by providing a toolset & calculus for formal power series. (see Bergeron-Labelle-Leroux and Joyal)

As it turns out, not only is species useful for manipulating generating functions, btu it provides this with a categorical approach that may be transplanted into other areas.

For the benefit of the entire audience, I shall introduce some definitions.

Definition: A category C is a collection of objects and arrows with each arrow assigned a source and target object, such that

 Gröbner bases for Operads — or what I did in my vacation

  • May 8th, 2009
  • 6:28 pm

This post is to give you all a very swift and breakneck introduction to Gröbner bases; not trying to be a nice and soft introduction, but much more leading up to announcing the latest research output from me.

Recall how you would run the Gaussian algorithm on a matrix. You’d take the leftmost upmost non-zero entry, divide its row by its value, and then use that row to eliminate anything in the corresponding column.

Once we have the matrix on echelon form, we can then do lots of things with it. Importantly, we can use substitution using the leading terms to do equation system solving.

The starting point for the theory of Gröbner bases was that the same method could be used – with some modification – to produce something from a bunch of polynomials that ends up being as useful as a row-reduced echelon form.

 PROPs and patches

  • February 15th, 2008
  • 7:59 pm

Brent Yorgey wrote a post on using category theory to formalize patch theory. In the middle of it, he talks about the need to commute a patch to the end of a patch series, in order to apply a patch undoing it. He suggests a necessary condition to do this is that, given patches P and Q, we need to be able to find patches Q’ and P’ such that PQ=Q’P’, and preferably such that Q’ and P’ capture some of the info in P and Q.

However, as such, this is not enough to solve the issue. For one thing, we can set Q’=P and P’=Q, and things are the way he asks for.

Now, I wonder whether we can solve this by using PROPs (or possibly di-operads or something like that). Let’s represent a document as a list of some sort of tokens. We’ll set D_n the set of all lists of length n, and we’ll set P_n^m to denote operations that take a list of length n and returns a list of length m.

 A-infinity and Hochschild cocycles

  • October 20th, 2006
  • 3:15 pm

This blogpost is a running log of my thoughts while reading a couple of papers by Bernhard Keller. I recommend anyone reading this and feeling interest to hit the arXiv and search for his introductions to A-algebras. Especially math.RA/9910179 serves as a basis for this post.

If you do enough of a particular brand of homotopy theory, you’ll sooner or later encounter algebras that occur somewhat naturally, but which aren’t necessarily associative as such, but rather only associative up to homotopy. The first obvious example is that of a loop space, viewed as a group: associativity only holds after you impose equivalence between homotopic loops.

 Report from Villars (5 in a series)

  • March 12th, 2006
  • 12:12 pm

For the last two half-days of the conference, I managed to take a break in skiing precisely when the conditions were at their very worst; with sight down to a few meters and angry winds. Miles Gould and Arne Weiner, however, managed to sit in a chair lift that kept stopping every 5 meters – AND they managed to break a T-bar lift. Suddenly the rope broke, they told me, and they had to ski down to the warden with the T-bar in the hand.

First out in this mathematical expose, though, is André Henriques, talking about

An operad coming from representation theory

There is a way to connect to a finite Lie algebra \mathfrac g first it’s universal enveloping algebra U\mathfrac g and quantum groups U_q\mathfrac g. From representations of U_q\mathfrac g, one path leads on over braided tensor products to braided tensor categories. Such categories are described by E_2 operads, which occur in the study of Gerstenhaber algebras and their homology.

 Report from Villars (4 in a series)

  • March 8th, 2006
  • 2:09 pm

I haven’t been able to get around to skiing since the last update – I may, or may not, go out in the slopes after this updates. The weather is growing warmer and wetter; and doesn’t really invite to skiing as it previously did.

However, we have had more talks. First out, yesterday evening, was Pascal Lambrechts

Coformality of the little ball operad and rational homotopy types of spaces of long knots

The theme of interest for this talk was long knots; i.e. embeddings of \mathbb R into \mathbb R^d such that outside some finite region in the middle, the embedding agrees with the trivial embedding t\mapsto(t,0,0,\dots,0). The space of all such is denote \mathcal L, and the item of study is more precisely the rational homology and rational homotopy of the fiber of the inclusion of \mathcal L into the space of all immersions of \mathbb R into \mathbb R^d.

 Report from Villars (3 in a series)

  • March 7th, 2006
  • 4:29 pm

This post will concern tuesday morning. Tuesday evening will be in a later post.

With the morning thus came, again, the pain in the legs. However, I’m told it’ll be better if I keep on skiing.

The mathematics in this report will come sooner than in the last; mainly because the lectures start at 8.30 and not at 17.00. :)

First out is Bênoit Fresse with

Little cubes operad actions on the bar construction of algebras

The reduced bar construcion of augmented associative algebras is given by fixing a field F, and for an augmented associative algebra A giving a chain complex B(A) such that B_n(A)=\hat A^{\otimes n} where \hat A denotes the augmentation ideal of A with the differential \partial(a_1\otimes\dots\otimes_n)=\sum_{i=1}^{n-1}a_\otimes\dots\otimes a_ia_{i+1}\otimes\dots\otimes a_n

If the product of A is commutative, then the shuffle product of tensors provides B(A) with the structure of a differential commutative algebra. In the talk, Fresse starts looking at the algebraic structure of B(A) for algebras with a homotopy commutative algebra:

 Report from Villars (2 in a series)

  • March 6th, 2006
  • 11:07 pm

So we hit the pistes during monday morning, those of us who actually already are here. Me, Bruno Vallette (Hi Stockholm!), Arne Weiner, Miles Gould, Paul Eugene Parents and Jonathan Scott, Dev Sinha and Muriel Livernet. Skiing was MARVELOUS. Me, Arne and Miles shot off on our own, and damn did we have a good time.

As I’m writing this, they’re still out there – I went back when the pain in my legs caused tears in my eyes for just turning on the skis. The techniques were solid as concrete. The muscles not so much. It took half an hour in the sauna to get to the point where I actually was able to walk again.

 Report from Villars (1 in a series)

  • March 5th, 2006
  • 8:37 pm

So, I’ve arrived in Villars sur Ollon for the Alpine Operad Workshop. The travel was long and at times annoying, mainly because the heavy snowfall over München and Zürich and some other places in the region triggered extreme delays. As we were supposed to board, the poor attendant at Nürnberg airport told us that the plane had not yet departed from Zürich.

Except for that, though, the travel went fine, and after being treated to some immensely beautiful views (glittering lake of Genéve with rows and rows of snowcovered grapevines in front, anyone?) and reminded of just how much I miss the deep-snow winters, I got up on this mountain in southwestern (very much frenchspeaking) Switzerland to the Hotel du Golf. The receptionist told me, straight off, that a number of my colleagues had already arrived, and then I went to eat (Crêpes – expensive and not even correctly delivered…) and started wrestling the connector dance. Y’see, half of the connectors used in civilized Europe work here. The other half don’t. And those who do work, only do work if they’re impeccably straight. So I had to work for quite a while to actually, y’know, get my laptop, my mp3player, my loudspeakers (I sleep with music, mmmkay? Headphones are NOT very nice to sleep in, mmmkay?) and my cell phone all connected. I think I disconnected 75% of the room lights in the process.

 Monads, algebraic topology in computation, and John Baez

  • February 21st, 2006
  • 11:06 am

Todays webbrowsing led me to John Baez finds in mathematical physics for week 226, which led me to snoop around John Baez homepage, which in turn led me to stumble across the Geometry of Computation school and conference in Marseilles right now.

This, in turn, leads to several different themes for me to discuss.

Cryptographic hashes

In the weeks finds, John Baez comes up to speed with the cryptographic community on the broken state of SHA-1 and MD-5. Now, this is a drama that has been developing with quite some speed during the last 1-1½ years. It all began heating up seriously early 2005 when Wang, Yin and Yu presented a paper detailing a serious attack against SHA-1. Since then, more and more tangible evidence for the inadvisability of MD-5 and upcoming problems with SHA-1 have arrived – such as several example objects with different contents and identical MD-5 hashes: postscript documents (Letter of Recommendation and Access right granting), X.509 certificates et.c.