Skip to main content

Section11.3Estimating Ramsey Numbers¶ permalink

We will find it convenient to utilize the following approximation due to Stirling. You can find a proof in almost any advanced calculus book.

\begin{equation*} n!\approx \sqrt{2\pi n} \left( \frac{n}{e}\right)^n\left(1+ \frac{1}{12n}+\frac{1}{288n^2}-\frac{139}{51840n^3} +O\left(\frac{1}{n^4}\right)\right). \end{equation*}

Of course, we will normally be satisfied with the first term:

\begin{equation*} n!\approx \sqrt{2\pi n} \left( \frac{n}{e}\right)^n \end{equation*}

Using Stirling's approximation and the binomial coefficients from the proof of Ramsey's Theorem for Graphs, we have the following upper bound:

\begin{equation*} R(n,n) \le \binom{2n-2}{n-1} \approx \frac{2^{2n}}{4\sqrt{\pi n}} \end{equation*}