Ramseyovské problémy

Rozhodněte, která z následujících tvrzení jsou pravdivá ($K_N$ značí úplný graf na množině vrcholů $\{0,1,\dots, N-1\}$):

1. Pro každé dostatečně velké $N \in \N$ platí, že když hrany $K_N$ obarvíme dvěma barvami, pak vždy bude existovat jednobarevný úplný podgraf na deseti vrcholech, který obsahuje vrchol číslo 0.
2. Pro každé dostatečně velké $N \in \N$ platí, že když hrany $K_N$ obarvíme dvěma barvami, pak vždy bude existovat jednobarevný úplný podgraf na deseti vrcholech, jehož každý vrchol je mocnina dvojky.
3. Trojbarevná verze: $\forall k,l,m \in \N: \exists N\in \N:$ $\forall$ obarvení hran $K_N$ červeně/modře/zeleně: $G$ obsahuje červený indukovaný podgraf na $k$ nebo modý na $l$ nebo zelený na $m$ vrcholech.
4. Vícebarevná: $\forall c, k \in \N: \exists N\in \N:$ $\forall$ obarvení $c$ barvami hran grafu $K_N$: $G$ obsahuje jednobarevný indukovaný podgraf na $k$ vrcholech.

Nekonečná Ramseyova věta

1. Dokažte, že v každé nekonečné posloupnost reálných čísel lze najít nekonečnou rostoucí podposloupnost, nekonečnou klesající podposloupnost, nebo nekonečnou konstantní podposloupnost.
2. Dokažte, že v každé spočetné nekonečné množině bodů v rovině lze najít nekonečně mnoho bodů, které všechny leží na společné přímce, nebo nekonečně mnoho bodů, z nichž žádné tři neleží na přímce.

Konečná šachovnice

Mějme „šachovnici“ tvaru $N\times N$ , pro nějaké $N \in \N$. Máme k dispozici $b$ barev a každé políčko šachovnice obarvíme některou z těchto barev. Dokažte, že pokud je $N$ dost velké v závislosti na $b$, tak platí následující:

1. Existuje deset políček ve stejném řádku, která mají všechna stejnou barvu.
2. Existují dva řádky a dva sloupce takové, že všechna čtyři políčka na jejich průsečících mají stejnou barvu.
3. Existuje deset řádků a deset sloupců takových, že všech 100 políček na jejich průsečících má stejnou barvu.

Jak velké N stačí k tomu, aby byla tvrzení splněná?

Nekonečná šachovnice

Mějme nyní nekonečnou „šachovnici“, jejíž řádky i sloupce jsou očíslované přirozenými čísly.

1. Ukažte, pro libovolné $m \in N$, že pokud libovolně obarvíme políčka této šachovnice dvěma barvami, tak bude existovat „jednobarevná podšachovnice tvaru $m \times \infty$“, tj. vždy půjde vybrat $m$ řádků a nekonečně mnoho sloupců tak, že jejich průsečíky budou mít všechny stejnou barvu.
2. Ukažte, že existuje obarvení políček nekonečné šachovnice dvěma barvami, ve kterém neexistuje „jednobarevná podšachovnice tvaru $\infty\times\infty$“, tj. nelze vybrat nekonečně mnoho řádků a nekonečně mnoho sloupců tak, aby všechna políčka na jejich průsečících měla stejnou barvu.