Feeds:
Posts
Comments

Posts Tagged ‘species theory’

The free cocompletion I

Posted in math.CO, math.CT, tagged , , on April 1, 2014| 10 Comments »

Let C be a (locally small) category. Recall that any such category naturally admits a Yoneda embedding

\displaystyle Y : C \ni c \mapsto \text{Hom}(-, c) \in \widehat{C}

into its presheaf category \widehat{C} = [C^{op}, \text{Set}] (where we use [C, D] to denote the category of functors C \to D). The Yoneda lemma asserts in particular that Y is full and faithful, which justifies calling it an embedding.

When C is in addition assumed to be small, the Yoneda embedding has the following elegant universal property.

Theorem: The Yoneda embedding Y : C \to \widehat{C} exhibits \widehat{C} as the free cocompletion of C in the sense that for any cocomplete category D, the restriction functor

\displaystyle Y^{\ast} : [\widehat{C}, D]_{\text{cocont}} \to [C, D]

from the category of cocontinuous functors \widehat{C} \to D to the category of functors C \to D is an equivalence. In particular, any functor C \to D extends (uniquely, up to natural isomorphism) to a cocontinuous functor \widehat{C} \to D, and all cocontinuous functors \widehat{C} \to D arise this way (up to natural isomorphism).

Colimits should be thought of as a general notion of gluing, so the above should be understood as the claim that \widehat{C} is the category obtained by “freely gluing together” the objects of C in a way dictated by the morphisms. This intuition is important when trying to understand the definition of, among other things, a simplicial set. A simplicial set is by definition a presheaf on a certain category, the simplex category, and the universal property above says that this means simplicial sets are obtained by “freely gluing together” simplices.

In this post we’ll content ourselves with meandering towards a proof of the above result. In a subsequent post we’ll give a sampling of applications.

(more…)

Read Full Post »

Update, and the combinatorics of quintic equations

Posted in math.CO, tagged , , on October 8, 2010| 5 Comments »

A brief update. I’ve been at Cambridge for the last week or so now, and lectures have finally started. I am, tentatively, taking the following Part II classes:

  • Riemann Surfaces
  • Topics in Analysis Probability and Measure
  • Graph Theory
  • Linear Analysis (Functional Analysis)
  • Logic and Set Theory

I will also attempt to sit in on Part III Algebraic Number Theory, and I will also be self-studying Part II Number Theory and Galois Theory for the Tripos.

As far as this blog goes, my current plan is to blog about interesting topics which come up in my lectures and self-study, partly as a study tool and partly because there are a few big theorems I’d like to get around to understanding this year and some of the material in my lectures will be useful for those theorems.

Today I’d like to blog about something completely different. Here is a fun trick the first half of which I learned somewhere on MO. Recall that the Abel-Ruffini theorem states that the roots of a general quintic polynomial cannot in general be written down in terms of radicals. However, it is known that it is possible to solve general quintics if in addition to radicals one allows Bring radicals. To state this result in a form which will be particularly convenient for the following post, this is equivalent to being able to solve a quintic of the form

\displaystyle y = 1 + xy^5

for y in terms of x. It just so happens that a particular branch of the above function has a particularly nice Taylor series; in fact, the branch analytic in a neighborhood of the origin is given by

\displaystyle y = \sum_{n \ge 0} \frac{1}{4n+1} {5n \choose n} x^n.

This should remind you of the well-known fact that the generating function \displaystyle y = \sum_{n \ge 0} \frac{1}{n+1} {2n \choose n} x^n for the Catalan numbers satisfies y = 1 + xy^2. In fact, there is a really nice combinatorial proof of the following general fact: the generating function \displaystyle y = \sum_{n \ge 0} \frac{1}{(k-1)n+1} {kn \choose n} x^n satisfies

y = 1 + xy^k.

(more…)

Read Full Post »

Newton’s sums, necklace congruences, and zeta functions

Posted in math.CO, math.NT, tagged , , , , , , on August 23, 2009| 6 Comments »

The goal of this post is to give a purely combinatorial proof of Newton’s sums which would have interrupted the flow of the previous post. Recall that, in the notation of the previous post, Newton’s sums (also known as the first Newton-Girard identity) state that

\displaystyle p_k - e_1 p_{k-1} \pm ... = (-1)^{k+1} ke_k.

One way to motivate a combinatorial proof is to recast the generating function interpretation appropriately. Given a polynomial C(t) with non-negative integer coefficients and C(0) = 0, let r_1, ... r_n be the reciprocals of the roots of C(t) - 1 = 0. Then

\displaystyle \frac{t C'(t)}{1 - C(t)} = \sum_{k \ge 1} p_k(r_1, ... r_n) t^k.

The left hand side of this identity suggests a particular interpretation in terms of the combinatorial species described by C(t). Today we’ll describe this species when C(t) is a polynomial with non-negative integer coefficients and then describe it in the general case, which will handle the extension to the symmetric function case as well.

The method of proof used here is closely related to a post I made previously about the properties of the Frobenius map, and at the end of the post I’ll try to discuss what I think might be going on.

(more…)

Read Full Post »

GILA VI: The cycle index polynomials of the symmetric groups

Posted in math.CO, tagged , on June 24, 2009| 7 Comments »

In the previous post we used the Polya enumeration theorem to give a sneaky, underhanded proof that

\displaystyle \sum_{m \ge 0} Z(S_m) t^m = \exp \left( z_1 t + \frac{z_2 t^2}{2} + \frac{z_3 t^3}{3} + ... \right).

If you’ve never seen the exponential function used like this, you might be wondering how it can be “explained.”

To explore this question, I’d like to give three other proofs of this result, the last of which will be “direct.” Along the way I’ll be attempting to describe some basic principles of species theory in an informal way. I’ll also give some applications, including to a Putnam problem.

(more…)

Read Full Post »