Feeds:
Posts

## 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 $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.)

## Structures on hom-sets

Suppose I hand you a commutative ring $R$. 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 $R$, and you also can’t refer directly to the multiplication or addition maps $R \times R \to R$, 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 $R$ as a set, and can you recover the ring operations on $R$?

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.

## 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.