Erdős–Szekeres theorem

[3/100%]

Show

LaTeX

Show LaTeX

Problem 1.3.7 from Глибичук А.А., Дайняк А.Б., Ильинский Д.Г., Купавский А.Б., Райгородский А.М., Скопенков А.Б., Чернов А.А. "Элементы дискретной математики в задачах" [ГДИ+16]More problems in Section 1.3 "The Pigeonhole Principle"

The natural numbers from 1 to 101 are written in some order. Prove that this sequence contains either an increasing or a decreasing subsequence of length 11.

Remark.

A subsequence is what is obtained from a sequence by deleting some of its terms.

Problem 4.3.2 from Глибичук А.А., Дайняк А.Б., Ильинский Д.Г., Купавский А.Б., Райгородский А.М., Скопенков А.Б., Чернов А.А. "Элементы дискретной математики в задачах" [ГДИ+16]More problems in Section 4.3 "Ramsey Numbers for Hypergraphs"

(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.4.4 from Глибичук А.А., Дайняк А.Б., Ильинский Д.Г., Купавский А.Б., Райгородский А.М., Скопенков А.Б., Чернов А.А. "Элементы дискретной математики в задачах" [ГДИ+16]More problems in Section 4.4 "Ramsey-Type Results"

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

An $m$ -cup ( $m$ -cap) is a subset of $m$ points of the graph of a convex (concave) function. Denote by $f(k, l)$ the minimal number $n$ such that among any $n$ points in the plane that have distinct abscissas, no three of which lie on a line, there is either a $k$ -cup or an $l$ -cap. (It is not obvious that such a number exists. Therefore a remark analogous to the one made in Problem 4.1.2(1) applies to the formulas in this problem.)

(1)

Among any $f(m, m)$ points in the plane there is a convex $m$ -gon. (Cf. Problem 4.3.2.)

(2)

$f(k, l) \leqslant f(k-1, l) + f(k, l-1) - 1$ .

(3)

$f(k, l) \leqslant \dbinom {k+l-4}{k-2} + 1$ .

(4)

$f(k, l) = \dbinom {k+l-4}{k-2} + 1$ .

References

[ГДИ+16] Глибичук А.А., Дайняк А.Б., Ильинский Д.Г., Купавский А.Б., Райгородский А.М., Скопенков А.Б., Чернов А.А. Элементы дискретной математики в задачах. МЦНМО, 2016.