Let be a (locally small) category. Recall that any such category naturally admits a Yoneda embedding
into its presheaf category (where we use to denote the category of functors ). The Yoneda lemma asserts in particular that is full and faithful, which justifies calling it an embedding.
When is in addition assumed to be small, the Yoneda embedding has the following elegant universal property.
Theorem: The Yoneda embedding exhibits as the free cocompletion of in the sense that for any cocomplete category , the restriction functor
from the category of cocontinuous functors to the category of functors is an equivalence. In particular, any functor extends (uniquely, up to natural isomorphism) to a cocontinuous functor , and all cocontinuous functors 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 is the category obtained by “freely gluing together” the objects of 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.
Read Full Post »
Something very unfortunate has happened: several things I have recently written that could have been blog entries are instead answers on math.SE! In the interest of exposition beyond the Q&A format I am going to “rescue” one of these answers. It is an answer to the following question, which I would like you to test your intuition about:
Flip coins. What is the probability that, at some point, you flipped at least consecutive tails?
Jot down a quick estimate; see if you can get within a factor of or so of the actual answer, which is below the fold.
Read Full Post »
I finally learned the solution to a little puzzle that’s been bothering me for awhile.
The setup of the puzzle is as follows. Let be a weighted undirected graph, e.g. to each edge is associated a non-negative real number , and let be the corresponding weighted adjacency matrix. If is stochastic, one can interpret the weights as transition probabilities between the vertices which describe a Markov chain. (The undirected condition then means that the transition probability between two states doesn’t depend on the order in which the transition occurs.) So one can talk about random walks on such a graph, and between any two vertices the most likely walk is the one which maximizes the product of the weights of the corresponding edges.
Suppose you don’t want to maximize a product associated to the edges, but a sum. For example, if the vertices of are locations to which you want to travel, then maybe you want the most likely random walk to also be the shortest one. If is the distance between vertex and vertex , then a natural way to do this is to set
where is some positive constant. Then the weight of a path is a monotonically decreasing function of its total length, and (fudging the stochastic constraint a bit) the most likely path between two vertices, at least if is sufficiently large, is going to be the shortest one. In fact, the larger is, the more likely you are to always be on the shortest path, since the contribution from any longer paths becomes vanishingly small. As , the ring in which the entries of the adjacency matrix lives stops being and becomes (a version of) the tropical semiring.
That’s pretty cool, but it’s not what’s been puzzling me. What’s been puzzling me is that matrix entries in powers of look an awful lot like partition functions in statistical mechanics, with playing the role of the inverse temperature and playing the role of energies. So, for awhile now, I’ve been wondering whether they actually are partition functions of systems I can construct starting from the matrix . It turns out that the answer is yes: the corresponding systems are called one-dimensional vertex models, and in the literature the connection to matrix entries is called the transfer matrix method. I learned this from an expository article by Vaughan Jones, “In and around the origin of quantum groups,” and today I’d like to briefly explain how it works.
Read Full Post »
The Hecke algebra attached to a Coxeter system is a deformation of the group algebra of defined as follows. Take the free -module with basis , and impose the multiplicative relations
if , and
otherwise. (For now, ignore the square root of .) Humphreys proves that these relations describe a unique associative algebra structure on with as the identity, but the proof is somewhat unenlightening, so I will skip it. (Actually, the only purpose of this post is to motivate the definition of the Kazhdan-Lusztig polynomials, so I’ll be referencing the proofs in Humphreys rather than giving them.)
The motivation behind this definition is a somewhat long story. When is the Weyl group of an algebraic group with Borel subgroup , the above relations describe the algebra of functions on which are bi-invariant with respect to the left and right actions of under a convolution product. The representation theory of the Hecke algebra is an important tool in understanding the representation theory of the group , and more general Hecke algebras play a similar role; see, for example MO question #4547 and this Secret Blogging Seminar post. For example, replacing and with and gives the Hecke operators in the theory of modular forms.
Read Full Post »
Before we define Bruhat order, I’d like to say a few things by way of motivation. Warning: I know nothing about algebraic groups, so take everything I say with a grain of salt.
A (maximal) flag in a vector space of dimension is a chain of subspaces such that . The flag variety of is, for our purposes, the “space” of all maximal flags. acts on the flag variety in the obvious way, and the stabilizer of any particular flag is a Borel subgroup . If denotes a choice of ordered basis, one can define the standard flag , whose stabilizer is the space of upper triangular matrices of determinant with respect to the basis . This is the standard Borel, and all other Borel subgroups are conjugate to it. Indeed, it’s not hard to see that acts transitively on the flag variety, so the flag variety can be identified with the homogeneous space .
Read Full Post »