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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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

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 524288 wierzchołkach zawiera jako podgraf indukowany:

klikę 𝒦9 lub antyklikę 𝒜9

klikę 𝒦10 lub antyklikę 𝒜10

klikę 𝒦512 lub antyklikę 𝒜512

klikę 𝒦1024 lub antyklikę 𝒜1024


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

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

dla dowolnej liczby naturalnej n graf 𝐆 zawiera jako podgraf indukowany klikę 𝒦n lub antyklikę 𝒜n

dla dowolnej liczby naturalnej n graf 𝐆 zawiera jako podgraf indukowany klikę 𝒦n oraz antyklikę 𝒜n

graf 𝐆 zawiera jako podgraf indukowany przeliczalną klikę 𝒦 lub przeliczalną antyklikę 𝒜


Dla dowolnych n,m,p istnieje liczba q taka, że:

dla każdego zbioru X o co najmniej q elementach i dowolnego rozbicia 𝒫n(X)=𝒜1𝒜m , istnieje p -elementowy podzbiór Y zbioru X taki, że 𝒫n(Y)𝒜i przy pewnym i=1,,t

dla każdego zbioru X o co najmniej n elementach i dowolnego rozbicia 𝒫r(X)=𝒜1𝒜t , istnieje q -elementowy podzbiór Y zbioru X taki, że 𝒫r(Y)𝒜i przy pewnym i=1,,t

dla każdego zbioru X o co najmniej q elementach i dowolnego rozbicia 𝒫n(X)=𝒜1𝒜m , istnieje q/m -elementowy podzbiór Y zbioru X taki, że 𝒫n(Y)𝒜p

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


Liczba Ramseya R(3,4) to:

6

9

14

co najwyżej 10


Liczba Ramseya Rr(4,4) spełnia:

Rr(4,4)Rr1(Rr(3,4),Rr(4,3))+1

Rr(4,4)Rr1(Rr(3,4),Rr(4,3))

Rr(4,4)Rr1(Rr1(3,4),Rr1(4,3))+1

Rr(4,4)Rr1(Rr1(3,4),Rr1(4,3))


Liczby Ramseya R(n,n) spełniają:

n2n/2(1e2o(1))R(n,n)

n22n(1e2o(1))R(n,n)

R(n,n)(2n2n1)

R(n,n)(2nn)