Upper bounds for $ES(n)$ from the first proof of Erdos and Székeres (1935)

Question

I'm studying the proof of Erdos and Székeres, from 1935. Both proofs are quite clear to me, specially the second (geometric) one, as its bounds on $ES(n)$. However, I can not see which bounds were found for $ES(n)$ in the first proof.

Could someone give me a hand clarifying it, please?

The original paper from Erdos and Székeres can be found here.

Answer 1

The bounds from the first proof are not immediately clear, because they depend on a second theorem: the hypergraph Ramsey theorem. That theorem says:

For all integers $i$, $k\ge i$, and $l\ge i$ there is an integer $m = m_i(k,l)$ with the following property. Whenever all the $i$-element subsets of an $m$-element set are colored red or blue, we can find either

1. A $k$-element subset such that all the $i$-element subsets within it are red, or

2. An $l$-element subset such that all the $i$-element subsets within it are blue.

The bound on $\operatorname{ESz}(n)$ obtained from the first proof is $m_4(5,n)$. The argument is that we let our set be a set of at least $m_4(5,n)$ points in the plane, color a $4$-element subset blue if its points form a convex quadrilateral, and red otherwise. By the hypergraph Ramsey theorem, there must either be a $5$-element subset whose $4$-element subsets are all red, or an $n$-element subset whose $4$-element subsets are all blue. The first case is impossible: any set of $5$ points contains $4$ that form a convex quadrilateral. Therefore the second case must be true, and the set of $n$ points we find will form a convex $n$-gon.

But now we need to figure out how big $m_4(5,n)$ is.

The good news is that we've reduced the problem to a more well-known and well-studied problem. The bad news is that the bounds we get are going to be terrible. You can look at a few of the bounds referenced in section 1.2 of this paper; we know that $m_4(5,n) \le 2^{2^{O(n^3 \log n))}}$, and it's conjectured that $m_4(5,n) \ge 2^{2^{\Omega(n)}}$. So we are getting doubly-exponential upper bounds from the first proof: much worse than the singly-exponential bounds from the second proof!