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

From Studia Informatyczne

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

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

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

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

któraś szuflada może być pusta


Graf o \displaystyle 524288 wierzchołkach zawiera jako podgraf indukowany:

klikę \displaystyle \mathcal{K}_{9} lub antyklikę \displaystyle \mathcal{A}_{9}

klikę \displaystyle \mathcal{K}_{10} lub antyklikę \displaystyle \mathcal{A}_{10}

klikę \displaystyle \mathcal{K}_{512} lub antyklikę \displaystyle \mathcal{A}_{512}

klikę \displaystyle \mathcal{K}_{1024} lub antyklikę \displaystyle \mathcal{A}_{1024}


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

istnieje liczba naturalna \displaystyle n\in\mathbb{N} taka, że graf \displaystyle \mathbf{G} zawiera jako podgraf indukowany klikę \displaystyle \mathcal{K}_{n} lub antyklikę \displaystyle \mathcal{A}_{n}

dla dowolnej liczby naturalnej \displaystyle n\in\mathbb{N} graf \displaystyle \mathbf{G} zawiera jako podgraf indukowany klikę \displaystyle \mathcal{K}_{n} lub antyklikę \displaystyle \mathcal{A}_{n}

dla dowolnej liczby naturalnej \displaystyle n\in\mathbb{N} graf \displaystyle \mathbf{G} zawiera jako podgraf indukowany klikę \displaystyle \mathcal{K}_{n} oraz antyklikę \displaystyle \mathcal{A}_{n}

graf \displaystyle \mathbf{G} zawiera jako podgraf indukowany przeliczalną klikę \displaystyle \mathcal{K}_{\mathbb{N}} lub przeliczalną antyklikę \displaystyle \mathcal{A}_{\mathbb{N}}


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

dla każdego zbioru \displaystyle X o co najmniej \displaystyle q elementach i dowolnego rozbicia \displaystyle \mathscr{P}_{n}\!\left( X \right)=\mathscr{A}_1\cup\ldots\cup\mathscr{A}_m , istnieje \displaystyle p -elementowy podzbiór \displaystyle Y zbioru \displaystyle X taki, że \displaystyle \mathscr{P}_{n}\!\left( Y \right)\subseteq \mathscr{A}_i przy pewnym \displaystyle i=1,\ldots,t

dla każdego zbioru \displaystyle X o co najmniej \displaystyle n elementach i dowolnego rozbicia \displaystyle \mathscr{P}_{r}\!\left( X \right)=\mathscr{A}_1\cup\ldots\cup\mathscr{A}_t , istnieje \displaystyle q -elementowy podzbiór \displaystyle Y zbioru \displaystyle X taki, że \displaystyle \mathscr{P}_{r}\!\left( Y \right)\subseteq \mathscr{A}_i przy pewnym \displaystyle i=1,\ldots,t

dla każdego zbioru \displaystyle X o co najmniej \displaystyle q elementach i dowolnego rozbicia \displaystyle \mathscr{P}_{n}\!\left( X \right)=\mathscr{A}_1\cup\ldots\cup\mathscr{A}_m , istnieje \displaystyle \left\lceil q/m \right\rceil -elementowy podzbiór \displaystyle Y zbioru \displaystyle X taki, że \displaystyle \mathscr{P}_{n}\!\left( Y \right)\subseteq \mathscr{A}_p

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


Liczba Ramseya \displaystyle {\sf R}\!\left( 3,4 \right) to:

\displaystyle 6

\displaystyle 9

\displaystyle 14

co najwyżej \displaystyle 10


Liczba Ramseya \displaystyle {\sf R}_{r}\!\left( 4,4 \right) spełnia:

\displaystyle {\sf R}_{r}\!\left( 4,4 \right)\leq {\sf R}_{{r-1}}\!\left( {\sf R}_{r}\!\left( 3,4 \right),{\sf R}_{r}\!\left( 4,3 \right) \right)+1

\displaystyle {\sf R}_{r}\!\left( 4,4 \right)\leq {\sf R}_{{r-1}}\!\left( {\sf R}_{r}\!\left( 3,4 \right),{\sf R}_{r}\!\left( 4,3 \right) \right)

\displaystyle {\sf R}_{r}\!\left( 4,4 \right)\leq {\sf R}_{{r-1}}\!\left( {\sf R}_{r-1}\!\left( 3,4 \right),{\sf R}_{r-1}\!\left( 4,3 \right) \right)+1

\displaystyle {\sf R}_{r}\!\left( 4,4 \right)\leq {\sf R}_{{r-1}}\!\left( {\sf R}_{r-1}\!\left( 3,4 \right),{\sf R}_{r-1}\!\left( 4,3 \right) \right)


Liczby Ramseya \displaystyle {\sf R}\!\left( n,n \right) spełniają:

\displaystyle n2^{n/2}\left( \frac{1}{e\sqrt{2}}-{\sf o}\!\left( 1 \right) \right)\leq{\sf R}\!\left( n,n \right)

\displaystyle n2^{2n}\left( \frac{1}{e\sqrt{2}}-{\sf o}\!\left( 1 \right) \right)\leq{\sf R}\!\left( n,n \right)

\displaystyle {\sf R}\!\left( n,n \right)\geq { 2n-2 \choose n-1 }

\displaystyle {\sf R}\!\left( n,n \right)\geq { 2n \choose n }