Skip to main content
Logo image

Applied Combinatorics

Section 11.3 Estimating Ramsey Numbers

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*}