8
$\begingroup$

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.

$\endgroup$

2 Answers 2

6
$\begingroup$

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<x<1$, 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.

$\endgroup$
2
  • $\begingroup$ Thank you so much! And sorry about the typo :') $\endgroup$
    – Robert
    Commented May 24 at 22:51
  • $\begingroup$ @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 $\endgroup$
    – Slugger
    Commented May 25 at 8:05
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$
    – Robert
    Commented May 24 at 22:50
  • $\begingroup$ 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. $\endgroup$ Commented May 25 at 17:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .