82
$\begingroup$

This is a question I've asked myself a couple of times before, but its appearance on MO is somewhat motivated by this thread, and sigfpe's comment to Pete Clark's answer.

I've often heard it claimed that combinatorial species are wonderful and prove that category theory is also useful for combinatorics. I'd like to be talked out of my skepticism!

I haven't read Joyal's original 82-page paper on the subject, but browsing a couple of books hasn't helped me see what I'm missing. The Wikipedia page, which is surely an unfair gauge of the theory's depth and uses, reinforces my skepticism more than anything.

As a first step in my increasing appreciation of categorical ideas in fields familiar to me (logic may be next), I'd like to hear about some uses of combinatorial species to prove things in combinatorics.

I'm looking for examples where there is a clear advantage to their use. To someone whose mother tongue is not category theory, it is not helpful to just say that "combinatorial structures are functors, because permuting the elements of a set A gives a permutation of the partial orders on A". This is like expecting baseball analogies to increase a brazilian guy's understanding of soccer. In fact, if randomly asked on the street, I would sooner use combinatorial reasoning to understand finite categories than use categories of finite sets to understand combinatorics.

Added for clarification: In my (limited) reading of combinatorial species, there is quite a lot going on there that is combinatorial. The point of my question is to understand how the categorical part is helping.

Improve this question
$\endgroup$
4
  • 12
    $\begingroup$ +1 for a really well-written question (not just "why X?" or "what is X?" or "someone told me X is cool, please tell me more") which will hopefully admit informative answers. $\endgroup$
    – Yemon Choi
    Commented Apr 24, 2010 at 23:42
  • 14
    $\begingroup$ This is slightly tangential, but what convinced me even more than André Joyal's paper is Andreas Blass's Seven Trees in One, which is a perfect illustration of how categorical thinking can lead to surprising combinatorial insight - ams.org/mathscinet-getitem?mr=1354064 $\endgroup$
    – François G. Dorais
    Commented Apr 24, 2010 at 23:53
  • $\begingroup$ I've been told that the combinatorial interpretation of the composition of generating functions was only made fully rigorous by species theory, but I can't actually back up that claim. $\endgroup$
    – Qiaochu Yuan
    Commented Apr 25, 2010 at 3:17
  • $\begingroup$ @Yemon: I wonder if we can make this a sample question for how to ask this sort of question on MO. $\endgroup$
    – Harry Gindi
    Commented Apr 25, 2010 at 3:18

9 Answers 9

Reset to default
30
$\begingroup$

Composition of species is closely related to the composition of symmetric collections of vector spaces ("S-modules"), which is a remarkable example of a monoidal category everyone who had ever encountered operads necessarily used. Applying ideas coming from this monoidal category interpretation has various consequences for combinatorics as well. For example, look at papers of Bruno Vallette on partition posets (here and here): I believe that already the description of the $S_n$ action on the top homology of the usual partition lattice was hard to explain from the combinatorics point of view - and for many other lattices would be impossible without the Koszul duality viewpoint.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ That's very interesting, Vladimir, thank you. Something like this is precisely what I was looking for: an application to "honest" combinatorics, like posets, and one where CT displayed a clear advantage. If MO will forgive an opinion, an uncomfortable proportion of the applications I had previously witnessed of CT to subjects S amounted to setting up categories in S, then proceeding to ask CT-questions inside of S, without regard to what the S-questions were. $\endgroup$
    – Pietro
    Commented Apr 25, 2010 at 23:50
  • 1
    $\begingroup$ I'm afraid I'm currently on the wrong side of Gowers's cohomology divide to properly appreciate what is being said about "top homology". But I'll try to understand at least one of the papers you mentioned and hopefully be the wiser for it. $\endgroup$
    – Pietro
    Commented Apr 25, 2010 at 23:52
  • 1
    $\begingroup$ Pietro, for an introduction to this area written by combinatorics people I suggest you have a look at the paper "Introduction to Cohen-Macaulay posets" by Bjorner, Garsia and Stanley. The reasons to study the group action on top homology of a CM poset are, for example, briefly discussed in Sec. 6b of that paper. $\endgroup$
    – Vladimir Dotsenko
    Commented Apr 26, 2010 at 8:11
  • 1
    $\begingroup$ I just saw this comment. Thanks for the pointer, Vladimir. Just a heads-up for anyone else reading this: it's much easier to find the paper if you replace "posets" with "partially ordered sets" in a Google search! $\endgroup$
    – Pietro
    Commented May 16, 2010 at 1:48
  • 1
    $\begingroup$ @SergeyDovgal done! as in, added links to arXiv (as opposed to Bruno's homepage). $\endgroup$
    – Vladimir Dotsenko
    Commented Feb 25, 2018 at 19:38
44
$\begingroup$

Let's start from the beginning. The main textbook on species is this one by Bergeron, Labelle, and Leroux, all major experts in the field. Even if you don't want to read the book, read the introduction by G.-C. Rota (which is interesting, enlightening and relatively short. In there, Rota writes:

"I dare make a prediction on the future acceptance of this book. At first, the old fogies will pretend the book does not exist. This pretense will last until sufficiently many younger combinatorialists publish papers in which interesting problems are solved using the theory of species. Eventually, a major problem will be solved in the language of species, and from that time on everyone will have to take notice."

It has been 13 years since these words had been written (almost to the day), so it is perhaps time to revisit this prediction. The "major problem" part clearly did not work out. One can argue that it's too soon to judge. Maybe. Maybe not. The first part, on "sufficiently many younger combinatorialists", is more interesting and probably arguable. There are sufficiently many people using and referencing the book - it has over 300 citations on GoogleScholar. And if you look at these citations, it becomes clear that the book has an extended influence over a large range of fields - the language and philosophy of species are clearly useful.

On the other hand, in comparison with the "competition", the theory of species is clearly not doing so well. Goulden & Jackson's "Combinatorial Enumeration" and Stanley's "Enumerative Combinatorics" have been cited about 1,000 times each (yes, both are older, but still). If you go a bit further away from the field, Alon & Spencer's "Probabilistic Method" has been cited over 3,000 times...

My conclusions: the answer to your question is both Yes and No. The theory of species is clearly useful, but more like a good language to use, or a guiding principle of which roads to take and which to stay clear of. When it comes to explicitly stated "practical" problems, people seem to prefer more directly applicable tools. I would compare this phenomenon to the influence of complexity theory on enumerative combinatorics: whatever you are enumerating, even if your problems are non-algorithmic and in a very classical combinatorial setting, it is still useful to know what is #P-completeness, simply because this gives you a different point of view on the objects you are enumerating, and sometimes it can also save you a bit of time by suggesting that the problem might be too general and thus have no explicit solution.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Also, I read Rota's intro before asking the question. I plan to look at this book on Monday. I must say I don't find this kind of generality terribly convincing. Defenses of "new mathematics", without caveats, fail to take into account the limitless possibilities mathematics, and our finite lifetimes. Of course one can't expect Rota to go into examples in a one-page introduction! Coming to MO, I was half-expecting someone to post a concrete, pretty application that made a lot of categorical ideas. Anyway, thanks again for your great answer! $\endgroup$
    – Pietro
    Commented Apr 25, 2010 at 7:27
  • 2
    $\begingroup$ If we're counting Google Scholar citations, Flajolet and Sedgewick's Analytic Combinatorics, published fifteen months ago, has 526. $\endgroup$
    – Michael Lugo
    Commented Apr 25, 2010 at 13:38
  • 1
    $\begingroup$ @Pietro No, I don't mean a close analogy with complexity - just on the level of heuristic and occasional formal application. I wanted to make this comparison since I think CS ideas are by far much better known now, and often taken for granted. When you realize that many CS ideas are less than 30 years old, you can see a profound but often very informal influence they had over our thinking. I think comb-sp influence is often just as informal, but on a much smaller scale, of course. $\endgroup$
    – Igor Pak
    Commented Apr 25, 2010 at 19:19
  • 4
    $\begingroup$ @Michael Right, this is actually another very good "competitor"... But "15 moths ago" is a bit misleading, I think. Versions of the book have been available on the web for maybe 10 years. Speaking of citations and to follow up on my CS comparisons, Garey & Johnson's 1979 book has been cited over 35,000 times! $\endgroup$
    – Igor Pak
    Commented Apr 25, 2010 at 19:28
  • 2
    $\begingroup$ Some chapters of Flajolet-Sedgewick were already available in 1994 (as they were writing them, I know Philippe would put them up on his web page, even back then.) [I was hosted in Flajolet's group 1993-1996] $\endgroup$
    – Jacques Carette
    Commented Apr 26, 2010 at 11:57
18
$\begingroup$

Pietro, if you haven't done so by now, you really, really ought to read Joyal's paper. (I can't understand why you would express skepticism before you'd even looked at the primary sources!)

If there is a single application of species to be singled out from this wonderful article, it is Joyal's proof of Cayley's theorem. (This proof was highlighted in Proofs from THE BOOK.) But this is only one of the treasures in the paper that await those who take the trouble to read it.

Much of the art of combinatorial thinking (at least in enumerative combinatorics) is knowing how to draw the correct pictures, and the theory of species can be seen as a step toward turning that art into a science, by formalizing directly the operations on structures which are implicitly coded by generating function techniques. In different words, the basic functional operations on exponential generating functions are lifted to functorial operations on species. At some level such insights must have been known to combinatorialists, but the theory of species serves to formalize them in the light of day, and no less a combinatorialist than Zeilberger has found species a significant source of inspiration.

Improve this answer
$\endgroup$
6
  • 4
    $\begingroup$ +1; Joyal's proof of Cayley's theorem is one of my favorite proofs. When I first saw it, I think I actually laughed out loud. $\endgroup$
    – Qiaochu Yuan
    Commented Mar 23, 2011 at 1:40
  • $\begingroup$ Yes, the proof, once understood, is unforgettable. $\endgroup$
    – Todd Trimble
    Commented Mar 23, 2011 at 1:52
  • 2
    $\begingroup$ But Joyal's proof does not use species. His proof may have been inspired by species, but his bijection is not natural (i.e., not functorial) — not that there's anything wrong with that. $\endgroup$
    – Ira Gessel
    Commented Oct 30, 2014 at 20:53
  • 2
    $\begingroup$ @IraGessel I don't have the paper in front of me, but my memory is that he does identify the functors (the species) that are involved, viz. the species of bipointed trees as $Lin \circ RTree$ and the species of endofunctions as $Perm \circ RTree$, both being instances of the functorial substitution product $\circ$ (here $RTree$ is the species of rooted trees, $Lin$ the species of linear orders, and $Perm$ the species of permutations). Of course it's true that the functors (the species) $Lin$ and $Perm$ are not naturally isomorphic. Otherwise I stand by my comment. $\endgroup$
    – Todd Trimble
    Commented Oct 30, 2014 at 21:26
  • $\begingroup$ OK, Joyal described his proof using species, but he used (implicitly) a non-natural bijection; more precisely, he used the fact that the number of linear orders of a finite set is equal to the number of permutations (i.e., sets of cycles) of the set, but the corresponding species are not isomorphic. The proof may have been inspired by species, but I don't think it's a good example of what species are good for. There are other ways to deal with exponential generating functions; the real power of species (at least in enumeration) is its application in enumeration under group action. $\endgroup$
    – Ira Gessel
    Commented Oct 31, 2014 at 2:34
10
$\begingroup$

The categorical perspective tells you why egf's have $n!$s in the denominator! A species can be thought of as describing a "graded groupoid," where the grade of degree $n$ is the groupoid consisting of the action of $S_n$ on the corresponding sets. The groupoid cardinality of a finite group $G$ acting on a finite set $X$ is just $\frac{|X|}{|G|}$, so the "graded groupoid cardinality" of a species is precisely its egf.

In cases like the Catalan numbers where the natural generating function is ordinary, what happens is that the action of $S_n$ is free. For example, the species corresponding to Catalan numbers really corresponds to labeled rooted binary trees, and $S_n$ acts on the labels. The resulting quotient counts unlabeled rooted binary trees, so the generating function appears ordinary.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ In "labeled rooted binary trees" you would probably add "planar"... $\endgroup$
    – Vladimir Dotsenko
    Commented Apr 25, 2010 at 22:02
9
$\begingroup$

Before I learned about species I didn't understand why you sometimes use exponential generating functions and sometimes ordinary ones. Now I understand: for species you should use exponential generating functions!

Improve this answer
$\endgroup$
3
  • $\begingroup$ Noah, I myself find gf's to be somewhat magical objects. It certainly never occurred to me to string out a sequence of numbers in a power series, until I saw it done. I guess this would have been a more natural thing to try for Euler. But knowing that they are worthy of study, I find the series of developments up to exponential gf's natural. It is sort of what comes out if you try to make the product of gf's mean something nice, and you get added benefits in the end. $\endgroup$
    – Pietro
    Commented Apr 25, 2010 at 8:32
  • 1
    $\begingroup$ I found that Stanley's books give a very good understanding and motivation for different gf's, including "denominators different from n!". Perhaps I'll glean a different perspective on Monday. Thanks for your input! $\endgroup$
    – Pietro
    Commented Apr 25, 2010 at 8:33
  • 5
    $\begingroup$ @Noah: my impression is to use exponential generating functions when objects are labeled (e.g. labeled trees, permutations, set partions,...) and ordinary generating functions for indistinguishable objects (unlabeled trees, number partitions,...) This impression came from a mixture of Stanley's book/classes and also the theory of species. $\endgroup$
    – Patricia Hersh
    Commented Oct 22, 2012 at 17:39
9
$\begingroup$

First of all I need to say that I know nothing about the achievements of category theory. So far, I couldn't get myself to discover any theorem, that proves something in, say, combinatorics, using category theory in an essential way. (Hints were given in some answers to this question, but I didn't have time to follow them yet.)

Furthermore, I have to admit that I don't know enough of the history, so I cannot claim that the following items are really achievements of a "categorical" point of view on combinatorial objects. One may argue that one doesn't need categorical language to phrase these concepts, and it seems to me that Bergeron, Labelle and Leroux have consciously avoided it. However, I think the "origin" of the ideas is of "categorical" spirit.

1) I'd say that the concept of equality of ordinary species, and, related to that, their molecular decomposition is something very important for it's own right, simply because it's beautiful. I'm not sure whether this concept has been fully exploited yet in a practical sense. Possibly it's hard to exploit because very often we encounter structures which are really unlabelled. I read about the desire to classify objects counted by the Catalan numbers every so often: there is little to be done with species, because their defining equation is algebraic. (I guess this doesn't preclude the existence of an interesting labelled object with isomorphism types being counted by the Catalan numbers, if you know of one, please share!)

2) tightly connected with the previous item is the very structured way to go about counting under group action. Nils de Bruijn wrote "this kind of enumeration theory is a matter of exposition and organisation of things which are in essence trivial". Here I think that in many cases, especially multivariate species are just the right tool. A concrete example: "how many possibilities are there to put two red, two blue and four green balls into a round and three square boxes?" Yes, it is easy to that, but with species it is trivial: we want the coefficient of $[R^2B^2G^4]$ in the isomorphism type series corresponding to $E_1(E(R+B+G)) E_3(E(R+B+G))$. Again: I would like to emphasise that species give the problem structure, and it would seem to me that this is at the heart of "categorical thinking", even if no category theory is involved.

3) there is at least one useful operation on species, which comes about very naturally, namely functorial composition.

4) this item is rather a question than an answer: operads have already been mentioned, does somebody know what Monoidal functors, species and Hopf algebras by Marcelo Aguiar and Swapneel Mahajan is about? Maybe that would "really" answer the original question...

Improve this answer
$\endgroup$
4
  • $\begingroup$ Does your recent arXiv preprint with Westbury warrant an update of this post? $\endgroup$
    – darij grinberg
    Commented May 3, 2015 at 5:07
  • 2
    $\begingroup$ Using an equivalence (between the category of invariant tensors and a diagram category) we transform the problem of determining a Frobenius character into a setting in which the language (and intuition) of species applies in an obvious way. I guess this indicates that category theory is useful for combinatorics. I'd also say that the paper advertises species: we give some proofs in two versions, using the language of representation theory and alternatively the language of species. I find the latter easier, of course. $\endgroup$
    – Martin Rubey
    Commented May 5, 2015 at 20:23
  • $\begingroup$ Very nice -- worth an edit of the post, I guess. $\endgroup$
    – darij grinberg
    Commented May 5, 2015 at 20:26
  • $\begingroup$ The Aguiar and Mahajan book is not at the above link, but can be found on Aguiar's Cornell page, and has appeared as CRMM 29. Here's the MSN link. $\endgroup$
    – LSpice
    Commented Feb 7, 2018 at 23:43
9
$\begingroup$

One further line of response would again invoke Rota:

"What can you prove with exterior algebra that you cannot prove without it?" Whenever you hear this question raised about some new piece of mathematics, be assured that you are likely to be in the presence of something important. In my time, I have heard it repeated for random variables, Laurent Schwartz' theory of distributions, ideles and Grothendieck's schemes, to mention only a few. A proper retort might be: "You are right. There is nothing in yesterday's mathematics that could not also be proved without it. Exterior algebra is not meant to prove old facts, it is meant to disclose a new world. Disclosing new worlds is as worthwhile a mathematical enterprise as proving old conjectures. (Indiscrete thoughts, p.48, Birkhauser, 1997).

For a couple of new worlds made possible by the species concept see:

1) M. Fiore, N. Gambino, M. Hyland and G. Winskel. The cartesian closed bicategory of generalised species of structures. Journal of the London Mathematical Society, 77(2) (2008), 203-220.

2) J. Baez et al. on stuff types (note, they call species 'structure types').

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ While I'm fond of that Rota quote, I'm not sure it really addresses the original question. The same book, to my slight amusement, later has a brief remark approving of some people disparaging the theory of distributions (quoting Calderon) $\endgroup$
    – Yemon Choi
    Commented Apr 26, 2010 at 8:37
  • 6
    $\begingroup$ No, it doesn't answer the original question, but it seems to me to be valid to respond to a question by suggesting a larger context. If you're not interested in the larger context, then the response won't be of interest to you. And you're also right to find Rota's utterances problematic. It is very reasonable to ask of something what can be proved with it which can't be proved without it. Of course, Rota only lists concepts which later turned out to be very valuable. There must be a heap of forgotten concepts which turned out to be of little value. $\endgroup$
    – David Corfield
    Commented Apr 26, 2010 at 10:34
  • $\begingroup$ I have a particular interest in this issue having looked into, and written about, the reception of the groupoid concept, which went through a period of "what can I do with them which I can't do with mere groups?" interrogation. $\endgroup$
    – David Corfield
    Commented Apr 26, 2010 at 10:36
6
$\begingroup$

To see a specific example of species applied to a fairly difficult enumeration problem (counting bipartite blocks), see my paper with Andrew Gainer-Dewar, Enumeration of Bipartite Graphs and Bipartite Blocks, Electronic Journal of Combinatorics, Volume 21, Issue 2 (2014) Paper #P2.40. If you're really serious you might compare our approach to counting bipartite graphs with Hanlon's.

Improve this answer
$\endgroup$
3
$\begingroup$

Since the Theory of species is also about relabeling, and relabellings form permutation groups, the Theory of Species is very close related to Permutation Groups theory. Is the theory of species a part of group theory ? NO. And if it were, someone should take it out of there and make it a standalone theory.

Imagine that someone wants to write a book containing equations like Part = E(E+), or that amazing Joyal' spines on Cayley formula. Then the author must write a lot of permutations stuff, leaving the formulas for the last chapter maybe, and confusing the reader: Is this book about permutations or about something else ?

The functorial definition avoid all the permutation trouble that would have been involved, including the definition of species on empty sets or the notion of copies of the empty set. A simple object like an empty box is not likely described by the mathematical empty set. Anyway, if there are still troubles with the empty sets and the void permutations, these are less visible in cats language.

Hence I think the main worry of the authors was to not reload the permutation group theory - and this is highly understandable. All the pieces of this mega combinatorial puzzle were already know : Burnside rings, wreath product, the fix of an element, Polya's polynomials on symmetries and the exponential generating functions. I also think that any presentation of Species should emphasize somehow the magic of egf calculus, that is for Combinatorics what the O and 1 calculus is for the true and false Logic.

Today, when many e.g.f.'s are listed, anyone could observe some "mysterious" relationships between egf's and it could build at least some mnemonic meanings that bring some orders in huge lists formulas. The Theory of Species tries to give a scientific base to this collection of mnemonic meanings. It is like someone invents the classical synthetic geometry after two thousands years of analytic Cartesian geometry and he try to well found it.

Bibliography http://www.math.sinica.edu.tw/www/file_upload/mayeh/1989Therelationsbetweenpermutation.pdf Labelle and Yeh in 1987 on Permutation groups and Species to all Species fans as I am -> I am also watching the talk page on wikipedia http://en.wikipedia.org/wiki/Talk:Combinatorial_species

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .