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 a nice exercise in asymptotics and the probabilistic method. (Also, it’s never explicitly given in Alon and Spencer.)

Read Full Post »

Structures on hom-sets

Suppose I hand you a commutative ring . I stipulate that you are only allowed to work in the language of the category of commutative rings; you can only refer to objects and morphisms. (That means you can’t refer directly to elements of , and you also can’t refer directly to the multiplication or addition maps , since these aren’t morphisms.) Geometrically, I might equivalently say that you are only allowed to work in the language of the category of affine schemes, since the two are dual. Can you recover as a set, and can you recover the ring operations on ?

The answer turns out to be yes. Today we’ll discuss how this works, and along the way we’ll run into some interesting ideas.

Read Full Post »

More about the Schrödinger equation on a finite graph

It looks like the finite graph model is not just a toy model! It’s called a continuous-time quantum random walk and is used in quantum computing in a way similar to how random walks on graphs are used in classical computing. The fact that quantum random walks mix sooner than classical random walks relates to the fact that certain quantum algorithms are faster than their classical counterparts.

I learned this from a paper by Lin, Lippner, and Yau, Quantum tunneling on graphs, that was just posted on the arXiv; apparently the idea goes back to a 1998 paper. I have an idea about another sense in which the finite graph model is not just a toy model, but I have not yet had time to work out the details.

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 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 »