Archive for the ‘graph theory’ Category

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.


Read Full Post »

Previously we described all finite-dimensional random algebras with faithful states. In this post we will describe states on the infinite-dimensional ^{\dagger}-algebra \mathbb{C}[x]. Along the way we will run into and connect some beautiful and classical mathematical objects.

A special case of part of the following discussion can be found in an old post on the Catalan numbers.


Read Full Post »

The goal of this post is to prove the following elementary lower bound for off-diagonal Ramsey numbers R(s, t) (where s \ge 3 is fixed and we are interested in the asymptotic behavior as t gets large):

\displaystyle R(s, t) = \Omega \left( \left( \frac{t}{\log t} \right)^{ \frac{s}{2} } \right).

The proof does not make use of the Lovász local lemma, which improves the bound by a factor of \left( \frac{t}{\log t} \right)^{ \frac{1}{2} }; nevertheless, I think it’s a nice exercise in asymptotics and the probabilistic method. (Also, it’s never explicitly given in Alon and Spencer.)


Read Full Post »

One of the most important discoveries in the history of science is the structure of the periodic table. This structure is a consequence of how electrons cluster around atomic nuclei and is essentially quantum-mechanical in nature. Most of it (the part not having to do with spin) can be deduced by solving the Schrödinger equation by hand, but it is conceptually cleaner to use the symmetries of the situation and representation theory. Deducing these results using representation theory has the added benefit that it identifies which parts of the situation depend only on symmetry and which parts depend on the particular form of the Hamiltonian. This is nicely explained in Singer’s Linearity, symmetry, and prediction in the hydrogen atom.

For awhile now I’ve been interested in finding a toy model to study the basic structure of the arguments involved, as well as more generally to get a hang for quantum mechanics, while avoiding some of the mathematical difficulties. Today I’d like to describe one such model involving finite graphs, which replaces the infinite-dimensional Hilbert spaces and Lie groups occurring in the analysis of the hydrogen atom with finite-dimensional Hilbert spaces and finite groups. This model will, among other things, allow us to think of representations of finite groups as particles moving around on graphs.


Read Full Post »

In the first few lectures of Graph Theory, the lecturer (Paul Russell) presented a cute application of Ramsey theory to Fermat’s Last Theorem. It makes a great introduction to the general process of casting a problem in one branch of mathematics as a problem in another and is the perfect size for a blog post, so I thought I’d talk about it.

The setup is as follows. One naive way to go about proving the nonexistence of nontrivial integer solutions to x^n + y^n = z^n, n > 2 (that is, solutions such that x, y, z are not equal to zero) is using modular arithmetic; that is, one might hope that for every n > 2 it might be possible to find a modulus m such that the equation has no nontrivial solution \bmod m. To simplify matters, we’ll assume that x, y, z are relatively prime to m, or else there is some subtlety in the definition of “nontrivial” (e.g. we might have x, y, z not divisible by m but x^n \equiv 0 \bmod m.) Note that it might be the case that m is not relatively prime to a particular nontrivial solution in the integers, but if we can prove non-existence of nontrivial solutions for infinitely many m (in particular, such that any integer is relatively prime to at least one such m) then we can conclude that no nontrivial integer solutions exist.

By the Chinese Remainder Theorem, this is possible if and only if it is possible with m a prime power, say m = p^k. If p is relatively prime to n, this is possible if and only if it is possible with m = p. This is because given a nontrivial solution \bmod p we can use Hensel’s lemma to lift it to a nontrivial solution \bmod p^k for any k (and even to \mathbb{Z}_p), and the converse is obvious. (Again to simplify matters, we’ll ignore the finitely many primes that divide n.) So we are led to the following question.

For a fixed positive integer n > 2 do there exist infinitely many primes p relatively prime to n such that x^n + y^n \equiv z^n \bmod p has no nontrivial solutions?

As it turns out, the answer is no. In 1916 Schur found a clever way to prove this by proving the following theorem.

Theorem: For every positive integer k there exists a positive integer m such that if \{ 1, 2, ... m \} is partitioned into k disjoint subsets A_1, ... A_k, then there exists i such that there exist a, b, c \in A_i with a + b = c. In other words, the Schur number S(k) = m exists. (Note that I am using a convention which is off by 1.)

If we let p be a prime greater than S(n) and let the A_i be the cosets of the subgroup of n^{th} powers in (\mathbb{Z}/p\mathbb{Z})^{*}, which has index at most n, we obtain the following as a corollary.

Corollary: Fix a positive integer n > 2. For any sufficiently large prime p, there exists a nontrivial solution to x^n + y^n \equiv z^n \bmod p.


Read Full Post »

Today we’re going to relate the representation graphs introduced in this blog post to something I blogged about in the very first and second posts in this blog! The result will be a beautiful connection between the finite subgroups of \text{SU}(2), the Platonic solids, and the ADE Dynkin diagrams. This connection has been written about in several other places on the internet, for example here, but I don’t know that any of those places have actually gone through the proof of the big theorem below, which I’d like to (as much for myself as for anyone else who is reading this).

Let G be a finite subgroup of \text{SL}_2(\mathbb{C}). Since any inner product on \mathbb{C}^2 can be averaged to a G-invariant inner product, every finite subgroup of \text{SL}_2(\mathbb{C}) is conjugate to a finite subgroup of \text{SU}(2), so we’ll suppose this without loss of generality. The two-dimensional representation V of G coming from this description is therefore faithful and self-dual. Consider the representation graph \Gamma(V), whose vertices are the irreducible representations of G and where the number of edges between V_i and V_j is the multiplicity of V_j in V_i \otimes V. We will see that \Gamma(V) is a connected undirected loopless graph whose spectral radius \lambda(\Gamma(V)) is 2. Today our goal is to prove the following.

Theorem: The connected undirected loopless graphs of spectral radius 2 are precisely the affine Dynkin diagrams \tilde{A}_n, \tilde{D}_n, \tilde{E}_6, \tilde{E}_7, \tilde{E}_8.

We’ll describe these graphs later; for now, just keep in mind that they are graphs with a number of vertices which is one greater than their subscript. In a later post we’ll see how these give us a classification of the Platonic solids, and we’ll also discuss other connections.


Read Full Post »

Recently I asked a question on MO about some computations I’d done with Catalan numbers awhile ago on this blog, and Scott Morrison gave a beautiful answer explaining them in terms of quantum groups. Now, I don’t exactly know how quantum groups work, but along the way he described a useful connection between walks on graphs and tensor products of representations which at least partially explains one of the results I’d been wondering about and also unites several other related computations that have been on my mind recently.

Let G be a compact group and let \text{Rep}(G) denote the category of finite-dimensional unitary representations of G. As in the finite case, due to the existence of Haar measure, \text{Rep}(G) is semisimple (i.e. every unitary representation decomposes uniquely into a sum of irreducible representations), and via the diagonal action it comes equipped with a tensor product with the property that the character of the tensor product is the product of the characters of the factors.

Question: Fix a representation V \in \text{Rep}(G). What is the multiplicity of the trivial representation in V^{\otimes n}?


Read Full Post »

Older Posts »


Get every new post delivered to your Inbox.

Join 325 other followers