RAMSEY-TÉTEL ÉS ALKALMAZÁSAI

Kezdjük magával a Ramsey-tétellel, illetve annak legáltalánosabb (?) formájával.

1.) Jelölje K_{n}^{r} az n pont összes r elemű részhalmazából álló hipergráfot, és p_{1}, …, p_{k} legyenek tetszőleges természetes számok. Ekkor létezik egy olyan (legkisebb) n = R_{k}^{r}(p_{1}, …, p_{k}) szám, az úgynevezett Ramsey-szám, melyre igaz az, hogy bárhogy színezzük k színnel K_{n}^{r} éleit, legalább egy i színre található p_{i} pont, melynek összes r elemű részhalmaza i színű.

2.) Színezzük az 1, …, n természetes számokat k színnel, ahol n ≥ k!e. Bizonyítsuk be, hogy léteznek olyan azonos színű x, y, z természetes számok, melyekre x + y = z.

3.) Színezzük az n elemű alaphalmaz részhalmazait k színnel, ahol n elég nagy. Bizonyítsuk be, hogy léteznek olyan azonos színű X, Y, Z részhalmazok, melyekre X ∪ Y = Z.

4.) Bizonyítsuk be, hogy létezik tetszőlegesen magas dimenziójú intervallumrendezés. (Egy részbenrendezett halmaz intervallumrendezés, ha megkapható, mint a számegyenes bizonyos intervallumainak részbenrendezése, ahol [a, b] > [c, d] akkor és csak akkor, ha a > d. Egy (S, >) részbenrendezett halmaz dimenziója az a legkisebb k, amelyre (S, >) megkapható, mint az S halmaz k különböző teljes rendezésének metszete.)

5.) Bizonyítsuk be, hogy a valós számok minden k^{2} + 1 tagú sorozata tartalmaz egy k + 1 tagú monoton részsorozatot.

6.) Bizonyítsuk be, hogy minden az {1, …, 2^{n}} halmazon értelmezett egész értékű f függvényhez, melyre 1 ≤ f(i) ≤ i, i = 1, …, 2^{n}, létezik olyan k + 1 tagú 1 = a_{1} < ⋯ < a_{n+1} ≤ 2^{n} sorozat, melyre f(a_{1}) ≤ ⋯ ≤ f(a_{n+1}).