## Cat urine backpack & relative differences of functions

Posted by – March 25, 2011

My backpack got stolen. It had just been urinated on by a cat, and was evidently beyond salvation (it was pretty beat up anyway). I emptied it and left it to stink outside of the pizzeria we’d decided to eat at, planning to take it to the next garbage bin I saw. But somebody nabbed it! I hope they don’t make the mistake I did of wearing the backpack – my nice winter coat now has a faint whiff of un-neutered male cat piss.

We were discussing Ramsey’s function (R(k) = the smallest number of people for which you can guarantee that either k people among them all know each other or k people all are strangers to each other) with Vadim. Its values are known to lie between ${\sqrt 2}^k$ and $4^k$, which is obviously quite a large gap. But how large? Vadim immediately said the difference $4^k- {\sqrt 2}^k$ is exponential, but it wasn’t so obvious to me. Eventually he convinced me. It then occurred to us that it’s in fact essentially $4^k$; given $a > b > 1$, the difference between the gap and the larger exponential function relative to the larger function goes to zero, $\lim_{x \to \infty} \frac{x^a - (x^a - x^b)}{x^a} = \lim_{x \to \infty} \frac{x^b}{x^a} = 0$. So when you subtract a smaller exponential function from a larger exponential function, you’ve basically subtracted nothing. Which is really a stupid thing to notice because it’s true even of polynomial functions (but not linear functions).