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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Komoda ma szuflad. Pierwsza jest w stanie pomieścić koszulę, druga i w ogólności -ta szuflada jest w stanie pomieścić koszul. Do przechowania jest 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 wierzchołkach zawiera jako podgraf indukowany:

klikę lub antyklikę

klikę lub antyklikę

klikę lub antyklikę

klikę lub antyklikę


Jeśli graf ma nieskończenie wiele wierzchołków, to:

istnieje liczba naturalna taka, że graf zawiera jako podgraf indukowany klikę lub antyklikę

dla dowolnej liczby naturalnej graf zawiera jako podgraf indukowany klikę lub antyklikę

dla dowolnej liczby naturalnej graf zawiera jako podgraf indukowany klikę oraz antyklikę

graf zawiera jako podgraf indukowany przeliczalną klikę lub przeliczalną antyklikę


Dla dowolnych istnieje liczba taka, że:

dla każdego zbioru o co najmniej elementach i dowolnego rozbicia , istnieje -elementowy podzbiór zbioru taki, że przy pewnym

dla każdego zbioru o co najmniej elementach i dowolnego rozbicia , istnieje -elementowy podzbiór zbioru taki, że przy pewnym

dla każdego zbioru o co najmniej elementach i dowolnego rozbicia , istnieje -elementowy podzbiór zbioru taki, że

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


Liczba Ramseya to:

co najwyżej


Liczba Ramseya spełnia:


Liczby Ramseya spełniają: