Math Problems Vault

Problem 4.3.1

Among any four of 8000 students one can choose a well-coordinated triple (i.e., a triple forming a well-coordinated team for a programming olympiad). Prove that one can choose 5 students any triple of whom is well-coordinated.

?

Problem 4.3.2

(1)(2)(3)(4)

?

(1)

Among any 5 points in general position in the plane there is a convex 4-gon.

(2)

There exist 8 points in general position in the plane among which there is no convex 5-gon.

(3)

Among any 9 points in general position in the plane there is a convex 5-gon.

(4)

Erdős–Szekeres Theorem. For some $n$ , among any $n$ points in general position in the plane there is a convex 10-gon. (Cf. Problem 4.4.4.)

The hypergraph Ramsey number $R_l(m_1, \ldots , m_k)$ , $m_1, \ldots , m_k \geqslant l$ , is the smallest positive integer $x$ such that for any coloring of all $l$ -element subsets of an $x$ -element set in $k$ colors there exist $i$ and a subset of size $m_i$ all of whose $l$ -element subsets are colored in the $i$ -th color. (Hypergraph Ramsey number'' is a single term defined above; knowing the term hypergraph'' is not needed to understand it.)

For example, it is obvious that $R_2(m_1, \ldots , m_k) = R(m_1, \ldots , m_k)$ and $R_3(3, n) = n$ . Problem 4.3.1 asks to prove that $R_3(5,4) \leqslant 8\, 000$ . And solving Problem 4.3.2(4) requires proving that $R_3(10,10)$ or $R_4(5,10)$ exists.

Problem 4.3.3

(1)(2)(3)

?

(1)

The number $R_l(m_1, \ldots , m_k)$ exists for any $m_1, \ldots , m_k$ . (This is not obvious!)

(2)

$R_l(m_1, \ldots , m_k) \leqslant R_l(R_l(m_1, m_2), m_3, \ldots , m_k)$ .

(3)

$R_l(m, n) \leqslant R_{l-1}(R_l(m-1, n), R_l(m, n-1)) + 1$ .

Problem 4.3.4

(1)(2)(3)

?

(1)

If $\binom {r}{n} < 2^{\binom {n}{3}-1}$ , then $R_3(n, n) > r$ .

(2)

There exists a number $c > 0$ such that $R_3(n, n) \geqslant 2^{cn^2}$ .

(3)

Find lower bounds on $R_l(\underbrace{n, \ldots , n}_{k})$ analogous to Statements 4.1.5(1, 2) (cf. Problem 4.2.7).

It is known that $R_l(\underbrace{n, \ldots , n}_{r^{2r}+1}) \geqslant (l-1)r^{r^{\cdots^{r}}}$ (a power tower of height $n$ ).