Matematyka dyskretna 2/Test 3: Własności podziałowe i Twierdzenie Ramsey'a

Komoda ma $10$ szuflad. Pierwsza jest w stanie pomieścić $1$ koszulę, druga $2$ i w ogólności $i$ -ta szuflada jest w stanie pomieścić $i$ koszul. Do przechowania jest $46$ koszul. Wtedy:

nie da się pomieścić wszystkich koszul w komodzie Źle

wszystkie szuflady będą w pełni zapełnione Źle

co najmniej jedna z szuflad będzie w pełni zapełniona Dobrze

któraś szuflada może być pusta Dobrze

Graf o $524288$ wierzchołkach zawiera jako podgraf indukowany:

klikę ${{𝒦}}_9$ lub antyklikę ${{𝒜}}_9$ Dobrze

klikę ${{𝒦}}_{10}$ lub antyklikę ${{𝒜}}_{10}$ Dobrze

klikę ${{𝒦}}_{512}$ lub antyklikę ${{𝒜}}_{512}$ Źle

klikę ${{𝒦}}_{1024}$ lub antyklikę ${{𝒜}}_{1024}$ Źle

Jeśli graf $\mathbf{𝐆}$ ma nieskończenie wiele wierzchołków, to:

istnieje liczba naturalna $n\in \mathbb{\mathbb{N}}$ taka, że graf $\mathbf{𝐆}$ zawiera jako podgraf indukowany klikę ${{𝒦}}_n$ lub antyklikę ${{𝒜}}_n$ Dobrze

dla dowolnej liczby naturalnej $n\in \mathbb{\mathbb{N}}$ graf $\mathbf{𝐆}$ zawiera jako podgraf indukowany klikę ${{𝒦}}_n$ lub antyklikę ${{𝒜}}_n$ Dobrze

dla dowolnej liczby naturalnej $n\in \mathbb{\mathbb{N}}$ graf $\mathbf{𝐆}$ zawiera jako podgraf indukowany klikę ${{𝒦}}_n$ oraz antyklikę ${{𝒜}}_n$ Źle

graf $\mathbf{𝐆}$ zawiera jako podgraf indukowany przeliczalną klikę ${{𝒦}}_{\mathbb{\mathbb{N}}}$ lub przeliczalną antyklikę ${{𝒜}}_{\mathbb{\mathbb{N}}}$ Dobrze

Dla dowolnych $n,m,p\in \mathbb{\mathbb{N}}$ istnieje liczba $q$ taka, że:

dla każdego zbioru $X$ o co najmniej $q$ elementach i dowolnego rozbicia Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{P}_{n}\!\left( X \right)=\mathscr{A}_1\cup\ldots\cup\mathscr{A}_m } , istnieje $p$ -elementowy podzbiór $Y$ zbioru $X$ taki, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{P}_{n}\!\left( Y \right)\subseteq \mathscr{A}_i } przy pewnym $i=1,\dots ,t$ Dobrze

dla każdego zbioru $X$ o co najmniej $n$ elementach i dowolnego rozbicia Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{P}_{r}\!\left( X \right)=\mathscr{A}_1\cup\ldots\cup\mathscr{A}_t } , istnieje $q$ -elementowy podzbiór $Y$ zbioru $X$ taki, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{P}_{r}\!\left( Y \right)\subseteq \mathscr{A}_i } przy pewnym $i=1,\dots ,t$ Dobrze

dla każdego zbioru $X$ o co najmniej $q$ elementach i dowolnego rozbicia Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{P}_{n}\!\left( X \right)=\mathscr{A}_1\cup\ldots\cup\mathscr{A}_m } , istnieje $\lceil q/m\rceil$ -elementowy podzbiór $Y$ zbioru $X$ taki, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \mathscr{P}_{n}\!\left( Y \right)\subseteq \mathscr{A}_p } Źle

Żadna z pozostałych własności nie musi zachodzić Źle

Liczba Ramseya $\mathsf{R}(3,4)$ to:

$6$ Źle

$9$ Dobrze

$14$ Źle

co najwyżej $10$ Dobrze

Liczba Ramseya ${\mathsf{R}}_r(4,4)$ spełnia:

${\mathsf{R}}_r(4,4)\le {\mathsf{R}}_{r-1}({\mathsf{R}}_r(3,4),{\mathsf{R}}_r(4,3))+1$ Dobrze

${\mathsf{R}}_r(4,4)\le {\mathsf{R}}_{r-1}({\mathsf{R}}_r(3,4),{\mathsf{R}}_r(4,3))$ Źle

${\mathsf{R}}_r(4,4)\le {\mathsf{R}}_{r-1}({\mathsf{R}}_{r-1}(3,4),{\mathsf{R}}_{r-1}(4,3))+1$ Źle

${\mathsf{R}}_r(4,4)\le {\mathsf{R}}_{r-1}({\mathsf{R}}_{r-1}(3,4),{\mathsf{R}}_{r-1}(4,3))$ Źle

Liczby Ramseya $\mathsf{R}(n,n)$ spełniają:

$n{2}^{n/2}(\frac{1}{e\sqrt{2}}-\mathsf{o}\left(1\right))\le \mathsf{R}(n,n)$ Dobrze

$n{2}^{2n}(\frac{1}{e\sqrt{2}}-\mathsf{o}\left(1\right))\le \mathsf{R}(n,n)$ Źle

$\mathsf{R}(n,n)\ge (\genfrac{}{}{0ex}{}{2n-2}{n-1})$ Dobrze

$\mathsf{R}(n,n)\ge (\genfrac{}{}{0ex}{}{2n}{n})$ Źle