Lower bounds on off-diagonal Ramsey numbers

The goal of this post is to prove the following elementary lower bound for off-diagonal Ramsey numbers (where is fixed and we are interested in the asymptotic behavior as gets large): The proof does not make use of the Lovász local lemma, which improves the bound by a factor of ; nevertheless, I think it’s [...]

Read Full Post »

The Schrödinger equation on a finite graph

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 [...]

Read Full Post »

Ramsey theory and Fermat’s Last Theorem

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, [...]

Read Full Post »

The McKay correspondence I

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 , the Platonic solids, and the ADE Dynkin diagrams. This connection has been written about [...]

Read Full Post »

Walks on graphs and tensor products

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 [...]

Read Full Post »

Newton’s sums, necklace congruences, and zeta functions

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 . One way to motivate a combinatorial proof is to [...]

Read Full Post »

The magic of the Frobenius map II

Once upon a time I discussed some interesting uses of the Frobenius map to solve some Putnam-style problems. Unfortunately, I wrote that post before becoming really interested in combinatorics, so I neglected to develop that particular side of the story, which I’d like to do now. The beginning of this story is the folklore combinatorial [...]

Read Full Post »

The Catalan numbers, regular languages, and orthogonal polynomials

I’ve been inspired by The Unapologetic Mathematician (and his pages and pages of archives!) to post more often, at least for the remainder of the summer. So here is a circle of ideas I’ve been playing with for some time. Let be the ordinary generating function for the ordered rooted trees on vertices (essentially we [...]

Read Full Post »

Dynkin diagrams and the Mahler measure problem

Funnily enough, a few days after I wrote the previous post, I was linked to a graph theory paper where one of the first results cited, which was clearly well-known to the authors, is the following remarkable generalization of what I tried to do: Theorem: The only connected simple graphs with spectral radius less than [...]

Read Full Post »

The spectral radius of a simple graph

I’ve decided not to port over the posts from AoPS. Among other things, I’d prefer to preserve the comments on older posts as they are. So here’s something I’ve been thinking about. Given a simple connected graph , define to be its largest positive eigenvalue; in other words, if counts the number of walks (equivalently, [...]

Read Full Post »