# Understanding a computation in a classic ramsey theory paper

I'm trying to understand the paper A note on Ramsey numbers by Ajtai, Komlos, and Szemeredi $$1983$$, and I am having trouble finding the "simple ( omitted ) calculation" in case $$1$$ of the proof of theorem $$2$$:

• The setup is as follows: Let $$G$$ be a triangle-free graph with $$n$$ vertices average degree $$t := \frac{1}{n}\sum_{v}d_{v} = 2\left\vert E\right\vert/n$$.

Define the function ( where $$\log$$ is the natural log ),

$$g(n,t) = 0.01\left(n/t\right) \log\left(t\right)$$ and fix some values of $$n$$ and $$t$$ where $$n,t \geq e^{99}$$. Now set $$n'=n-1$$ and $$t' \leq t(n-2)/(n-1)$$. We may also assume $$t',n' \geq e^{99}$$. Then, the paper claims, $$g(n',t') \geq g(n,t).$$

I spent many hours on many attempts, but this is the most promising: I assume $$t'=t(n-2)/(n-1)$$ for simplicity and with some algebra get, \begin{align*} g(n',t') &= \frac{(n-1)^2}{100(n-20)} \cdot \frac{\log(\frac{t(n-2)}{n-1})}{t} \newline &= \frac{n-22+\frac{361}{n-20}}{100} \cdot \frac{\log t + \log(\frac{n-20}{n-1})}{t} \newline &= \frac{1}{100} \left( n \log t + n \log\left(\frac{n-20}{n-1}\right) - 22 \log t - 22 \log \left(\frac{n-20}{n-1}\right) + \frac{361}{n-2} \log t + \frac{361}{n-2} \log\left(\frac{n-20}{n-1}\right) \right) \newline &= g(n,t) + \frac{1}{100} \left( (n+22-\frac{361}{n-20}) \cdot \log \left(\frac{n-1}{n-20}\right) + \left(\frac{361}{n-20}-22\right) \cdot \log t \right) \end{align*} At this point, I believe all the terms multiplied by $$\log((n-1)/(n-20))$$ are very close to 0 except for $$n \log((n-1)/(n-20))$$ which I believe is approximately 19 (when $$n$$ is very large, which it is). Also, $$361/(n-20)$$ should be very close to 0, so I write $$g(n',t') > g(n,t) + \frac{1}{100}\left( n \log \left( \frac{n-1}{n-20} \right) - 22 \log t\right),$$ but the second term is negative for even moderately large $$t$$, and I don't think I have made any too lossy approximations to get here.

I believe either I have made some error in my approximations above, or there is way to use the relationship between the number of vertices in a graph and it's average degree which I am missing.

Additionally, since $$G$$ is assumed to be triangle free, using Mantel's theorem, $$|E| \leq \frac{n^2}{4} \quad \rightarrow \quad t \leq n/2.$$ However, I am not sure if this inequality helps. It seems implicit in the paper that the triangle-freeness of $$G$$ is unused for this computation since it is only explicitly stated to be used in the next case of the proof.

I would greatly appreciate any advice. :) I hope it is clear that this is not a homework problem.

Importantly, the paper says that $$t' \leq t(n-20)/(n-1)$$, you have a typo in your bound.

Maybe its convenient to rearrange as follows: we forget the $$0.01$$, and will instead try to prove the equivalent $$\frac{n-1}{n}\log t' \geq \frac{t'}{t} \log t$$ Lets indeed use $$t' = t (n-20)/(n-1)$$. Now if we instead show that $$\frac{n-1}{n}\log t' \geq \frac{n-20}{n-1} \left(\log t' +\log\frac{n-1}{n-20} \right)$$ then we are done. The function $$x \log (1/x)$$ is at most $$1-x$$ for $$0, so that $$\frac{n-20}{n-1} \log \frac{n-1}{n-20} < 1 - \frac{n-20}{n-1} = \frac{19}{n-1} .$$ So we look to show that $$\frac{n-1}{n}\log t' \geq \frac{n-20}{n-1} \log t' + \frac{19}{n-1}.$$ We rearrange to

$$\left(\frac{n-1}{n} -\frac{n-20}{n-1} \right)\log t' \geq \frac{19}{n-1}.$$

This simplifies to $$\frac{1+18n}{n} \log t' \geq 19.$$ By $$t',n > e^{99}$$, this is true.

Edit I've spent some time working in combinatorics and its always very annoying when writers omit a calculation and add insult to injury by saying that it is simple

2nd Edit To be complete, we should probably mention something about selecting $$t'$$ equal to its upper bound. Namely, that $$g(n,t)$$ is decreasing in $$t$$ for $$t$$ large.

• Thank you so much! And sorry about the typo :') Commented May 24 at 22:51
• @Robert No problem. I think it is a good idea that you are doing these omitted calculations in papers, such bounds and inequalities pop up everywhere in Ramsey theory Commented May 25 at 8:05

Here's how I would verify this inequality when reading a paper. Clearly the $$e^{99}$$ is superfluous, and we should just think of $$n$$ and $$t$$ as being sufficiently large. This opens up some approximations for us to use with the knowledge that we could be more rigorous if we want to.

The question is, given $$n$$ and $$t$$ sufficiently large, for what $$t'$$ does $$n \frac{\log t}{t} \leq (n-1) \frac{\log t'}{t'}$$ hold? Taking logs, this is equivalent to $$\log\left( \frac{\log(t)}{t} \right) - \log\left( \frac{\log(t')}{t'} \right) \leq \log\left( 1 - \frac{1}{n} \right) .$$ Since $$n$$ is large, we use $$\log(1-1/n) \approx -1/n$$, and assuming $$t$$ and $$t'$$ are not too far apart, the left side can be approximated by a derivative. The derivative of $$\log(\log(x)/x)$$ is $$\frac{1-\log(x)}{x\log(x)}$$, which is approximately $$-1/x$$ for $$x$$ large. Our inequality becomes approximately $$-(t-t')/t \leq -1/n ,$$ or $$t' \leq t(1-1/n)$$. We check that $$t$$ and $$t'$$ are not too far apart as long as $$t \ll n$$ (which it is in this context).

This tells us the answer to first order. Now if we want to be correct (as one tries to be when writing a paper), we can replace these approximations with inequalities. For example, we have $$\log(1-1/n) \geq -2/n$$ for all $$n \geq 2$$. For the derivative approximation, you might invoke Taylor's Theorem to bound the error estimate. I would only actually sort out all of this if I was writing the paper -- when reading a paper, the first order estimates are enough to convince me that things work out.

Really the moral of this calculation is that when $$t \ll n$$, we can safely ignore the $$\log(t)$$ factor.

• Thanks so much, this was really insightful! I'm confused what you mean by $t \ll n$, as far as I see $t$ could be as large as $n/2$, and normally I think of $\ll$ as meaning $t/n \to 0$. Commented May 24 at 22:50
• If my memory serves correctly, later in the paper they take $t$ to be on the order of $\sqrt{n}$. At any rate, this is clearly not a requirement for the inequality to hold as the other answer shows. Commented May 25 at 17:26