Question about a result in an article by Erdős on Ramsey theory

70 Views Asked by At

I'm finding very hard to understand a result by Erdős on a paper from 1947 titled "Some Remarks on the Theory of Graphs" that states:

Define $A(n)$ as the greatest integer such that given any graph $G$ of $n$ vertices, either it or its complementary graph contains a complete subgraph of order $A(n)$. Then for $3\leq A(n)$

$\frac{log\ n}{2log\ 2}<A(n)<\frac{2log\ n}{log\ 2}$

The proof follows immediately from Theorem I. $(4^{A(n)}>n,\ 2^{A(n)/2}<n)$

Theorem I refers to the main result of the article which gives some elementary bounds for Ramsey numbers. (I adapted the notation so that it resembles the more modern one).

Theorem I.
Let $k\ge3$. Then $2^{k/2}<R(k, k)\le {2k-2\choose k-1}<4^{k-1} $

Then, an obvious way of applying this result to the first statement would be if $R(A(n), A(n)) = n$.

But why is that true? I can't seem to point out why.

Also, is $A(n)$ some sort of inverse Ramsey number?