Proste oszacowanie dolne liczb Ramsey'a

[Wlodzimierz Holsztynski]

Proste oszacowanie dolne liczb Ramsey'a
=======================================

Dwukolorowaniem zbioru S nazywamy
dowolna funkcje:

bw : S --> {0 1}

Podzbior T zbioru dwukolorowego (S bw)
nazywamy monochromatycznym, jezeli bw|T
jest funkcja stala. Jezeli stala wartosc jest
rowna 0, to zbior T nazywamy czarnym, a
gdy 1 -- to bialym.

Niech X bedzie zbiorem, k -- liczba
kardynalna. Wtedy (X ## k) oznacza
rodzine wszystkich podzbiorow A zbioru X,
o mocy |A| = k.

Niech liczba n >/ k bedzie skonczona. Zbior X
nazwiemy (k n)-duzym, jezeli |X| >/ n oraz
dla kazdego dwukolorowania bw zbioru
S := (X ## k) istnieje zbior Y w (X ## n),
taki ze zbior T := (Y ## k) jest monochromatyczny.
W przeciwnym wypadku zbior X nazywamy
(k n)-malym -- wtedy istnieje dwukolorowanie bw
zbioru S, takie ze zaden zbior (Y ## k) nie
jest monochromatyczny, gdy Y nalezy do (X ## n).

W niniejszej nocie przez liczbe Ramsey'a rm(k n)
rozumiemy najmniejsza liczbe kardynalna r taka,
ze zbior X, o mocy |X| = r, jest (k n)-duzy..

Ramsey udowodnil, ze wszystkie liczby Ramsey'a
sa skonczone. Najpopularniejsze twierdzenie
ramsey'owskie mowi, ze rm(2 3) = 6: jak nie
pomalowac krawedzie grafu pelnego, o 6 wierzcholkach,
to zawsze powstanie bialy albo czarny trojkat..

*************************************

ZADANIE (pomaga zapamietac pojecia)

rm(1 n) = 2*n-1 dla n=1 2 ...

ZADANIE (daje poczatek indukcjom)

rm(k k) = k dla k=1 2 ...

*************************************

W swietle ostatniego zadania, odtad bez zalu zalozmy,
ze n > k > 0.

Niech A nalezy do (X ## n). Kazde dwukolorowanie
zbioru (A ## k) mozna przedluzyc na

ext := 2 ^ ((x ## k) - (n ## k))

dwukolorowan calego zbioru S := (X ## k), gdzie
x := |X| >/ n. Zatem istnieje dokladnie 2*ext
dwukolorowan zbioru S := (X ## n), dla ktorych
(A ## k) jest monochromatyczne. Istnieje
wiec nie wiecej (a nawet mniej) niz

2*ext * (x ## n)

dwukolorowan, dla ktorych istnieje monochromatyczny
zbior (A ## k), taki ze A nalezy do (X ## n).
Jezeli wiec liczba ta jest mniejsza od wszystkich
dwukolorowan zbioru S, to istnieje dwukolorowanie
zbioru S, dla ktorego nie istnieje A w (X ## n)
takie, ze (A ## k) jest monochromatyczne, czyli
taki X jest (k n)-maly. Dzieje sie wiec tak, gdy:

2*ext * (x ## n) < 2^(x ## k)

lub rownowaznie:

(i) (x ## n ) < 2 ^ ((n ## k) - 1)

Udowodnilismy:

TWIERDZENIE 1
=============
Gdy zachodzi powyzsza nierownosc (i), to zbior X,
o mocy |X|=x, jest (k n)-maly.

Poniewaz (x ## n) < x^n / n!, to zachodzi:

TWIERDZENIE 2
=============

rm(k n) > (n! * 2^((n ## k) - 1))^(1/n)

******************

Prawa strone mozemy napisac w postaci

n!^(1/n) * 2^(((n ## k) - 1)/n)

Ze wzoru Stirlinga wiemy, ze n!^(1/n) jest
rzedu n/e; a drugi czynnik (potega dwojki)
jest rzedu 2^(C*n^(k-1)) przy ustalonym k,
gdy n rosnie do nieskonczonosci. Widzimy tez
jak wielkie musi byc rm(n k), gdy na przyklad
n=2*k jest spore i rosnie do nieskonczonosci.
Bowiem (2*k ## k) > (4^k)/(2*k+1) dla k=1 2 ...
Tak wiec prawy czlon dla n=2*k jest
rzedu 2^((C*4^k / k^2), a wiec niezly z niego
dinozaur.

PRZYKLAD Dla k:=4 oraz n:=8 mamy:

(n ## k) - 1 = 69

oraz

(345002 ## 4) < 2^69 < (345003 ## 4)

Na mocy Tw. 1 (patrz tez (i)), zbior X o
34502 elementach jest (4 8)-maly, czyli

rm(4 8) >/ 345003

************

Wlodzimierz Holsztynski

PS. Powyzsza metoda jest az brutalnie prymitywna,
ale o dziwo daje z grubsza dobry rzad (bardzo
z grubsza). Nieco bardziej zlozony argument daje
mi nieco lepszy wynik, co moze wkleje tu. W pelni
po danej linii nalezy chyba stosowac glebsze,
probabilistyczne metody/wyniki.

[Marcin Kysiak]

Post by Wlodzimierz Holsztynski
Proste oszacowanie dolne liczb Ramsey'a
=======================================
Dwukolorowaniem zbioru S nazywamy
bw : S --> {0 1}
Podzbior T zbioru dwukolorowego (S bw)
nazywamy monochromatycznym, jezeli bw|T
jest funkcja stala. Jezeli stala wartosc jest
rowna 0, to zbior T nazywamy czarnym, a
gdy 1 -- to bialym.
Niech X bedzie zbiorem, k -- liczba
kardynalna. Wtedy (X ## k) oznacza
rodzine wszystkich podzbiorow A zbioru X,
o mocy |A| = k.

To się często w teorii mnogości oznacza przez [X]^k.

Post by Wlodzimierz Holsztynski
Niech liczba n >/ k bedzie skonczona. Zbior X
nazwiemy (k n)-duzym, jezeli |X| >/ n oraz
dla kazdego dwukolorowania bw zbioru
S := (X ## k) istnieje zbior Y w (X ## n),
taki ze zbior T := (Y ## k) jest monochromatyczny.
W przeciwnym wypadku zbior X nazywamy
(k n)-malym -- wtedy istnieje dwukolorowanie bw
zbioru S, takie ze zaden zbior (Y ## k) nie
jest monochromatyczny, gdy Y nalezy do (X ## n).

Znowu wtręt terminologiczny. Często stosowana notacja to:

\kappa --> (\lambda)^k_l

na skrót zapisu, że dla każdego kolorowania k-elementowych podzbiorów
zbiowu mocy \kappa na l kolorów istnieje zbiór monochromatyczny mocy
\lambda.

Post by Wlodzimierz Holsztynski
W niniejszej nocie przez liczbe Ramsey'a rm(k n)
rozumiemy najmniejsza liczbe kardynalna r taka,
ze zbior X, o mocy |X| = r, jest (k n)-duzy..
Ramsey udowodnil, ze wszystkie liczby Ramsey'a
sa skonczone. Najpopularniejsze twierdzenie
ramsey'owskie mowi, ze rm(2 3) = 6: jak nie
pomalowac krawedzie grafu pelnego, o 6 wierzcholkach,
to zawsze powstanie bialy albo czarny trojkat..

Czyli - w szczególności - dla każdego l\in N istnieje k\in N takie, że

k --> (l)^2_2.

Jest to tzw. skończone twierdzenie Ramsey'a.

Włodek zmierza w stronę skończonych liczb Ramseya, co stanowi mocną
teorię. Ja wspomnę o kilku wynikach dot. liczb nieskończonych - to też
jest piękna teoria obfitująca w eleganckie pomysły kombinatoryczne.

Otóż po pierwsze:

\aleph_0 --> (\aleph_0)^2_2.

Jest to nieskończone twierdzenie Ramsey'a; bardzo dobre ćwiczenie, wbrew
pozorom chyba łatwiejsze od skończonego.

Po drugie:

\aleph_1 -/-> (\aleph_1)^2_2, a nawet

c -/-> (\aleph_1)^2_2.

To zauważył chyba Sierpiński i jest to również proste. Jak będzie
zapotrzebowanie, to mogę ujawnić odpowiedź ;-) Natomiast przekreślenie
strzałki znika, gdy zaczynamy rozważać kolorowania par liczb
rzeczywistych, a na kolorowanie dorzucimy pewne warunki związane ze
strukturą prostej jako przestrzeni metrycznej czy przestrzeni z miarą.

Natomiast

c+ --> (\aleph_1)^2_2,

ogólnie

(2^\kappa)+ --> (\kappa+)^2_2.

To jest twierdzenie Erdosa--Rado.

Czyli znamy na razie tylko jedną liczbę nieskończoną \kappa taką, że
\kappa --> (\kappa)^2_2. Następna po \aleph_0 taka liczba musi już być
bardzo duża. W szczególności musi być silnie nieosiągalna.

Własność \kappa --> (\kappa)^2_2 wiąże się też z uogólnieniem tw.
Koeniga (każde drzewo o \aleph_0 wierzchołkach i skończonych stopniach
rozgałęzienia ma nieskończoną gałąź) na wyższe moce.

Pozdrawiam
Marcin

[Wlodzimierz Holsztynski]

Post by Marcin Kysiak
\aleph_0 --> (\aleph_0)^2_2.
Jest to nieskończone twierdzenie Ramsey'a;

Po ludzku: Pomalujmy kazda pare {x y}
liczb naturalnych x y na bialo lub na czarno
(mozna geometrycznie myslec, ze x y
polaczone sa krawedzia, ktora malujemy
na jeden z kolorow). Wtedy twierdzenie
mowi, ze istnieje nieskonczony podzbior A
liczb naturalnych taki, ze wszystkie pary
{x y}, gdzie x y \in A, sa pomalowane na ten
sam kolor.

Twierdzenie dopuszcza naturalny dowod, jakby
samo sie dowodzilo. Podam kilkanascie linijek
ponizej dowod, gdyby ktos chcial sie w tym momencie
zatrzymac i samemu dowod sobie wymyslec.

|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|

Dowod:

Niech a(0) bedzie dowolna liczba naturalna.
Nieskonczenie wiele krawedzi o koncu w a(0)
jest tego samego koloru, powiedzmy ze czarnego
(nie wykluczone, ze bialych krawedzi o koncu
w punkcie a(0) tez jest nieskonczenie wiele,
ale to nas nie obchodzi).

Budujmy, krok po kroku, poki to mozliwe, ciag
punktow a(k) i nieskonczonych zbiorow liczb
naturalnych A(k):

a(0) A(0) ... a(n) A(n) ...

takich, ze kazdy zbior A(k) zawiera sie w poprzednim,
podobnie a(k) \in A(k-1) dla k=1 2 ..., oraz kazda
para {a(k) y} jest pomalowana na czarno dla kazdego
y \in A(k), k=0 1 ...

(Dodam pedantycznie, co mozna
zalozyc, ze a(k) nie nalezy do A(k)).

Jezeli ciag ...a(n) A(n)..., liczb i zbiorow jest
nieskonczony, to kazda para liczb ze zbioru
{a(0) a(1) ...} jest pomalowana na czarno, wiec
twierdzenie zachodzi.

W przeciwnym wypadku natknelismy sie na
zbior B := A(n) taki, ze dla kazdego x \in A(n)
istnieje co najwyzej skonczenie wiele y \in A(n)
takich, ze krawedz {x y} jest czarna. Wtedy
niech b(0) \in B bedzie dowolne oraz (indukcja)
niech b(k) bedzie najmniejsza liczba naturalna
w zbiorze B, taka ze krawedz {b(j) b(k)} jest biala
dla kazdego j=0 ... k-1, dla k > 0. Dostalismy
nieskonczony zbior {b(0) b(1) ...} taki, ze
kazda jego krawedz {b(j) b(k)} jest pomalowana
na bialo. KONIEC DOWODU

Post by Marcin Kysiak
\aleph_1 -/-> (\aleph_1)^2_2, a nawet
c -/-> (\aleph_1)^2_2.
To zauważył chyba Sierpiński i jest to również proste.

Bylem obecny na uroczystym obchodzie 60-lecia (?)
pracy naukowej Profesora Waclawa Siepinskiego,
i wlasnie wtedy uslyszalem o tym jego twierdzeniu
i dowodzie powyzej--nawet nie pamietam, czy
bylo podane z mownicy, czy tez ktos podzielil
sie nim kolo mnie, na widowni (chyba z mownicy,
a komentarze padly prywatnie--pamietam JM,
ktory stwierdzil, ze ten wynik i dowod jest dla
W.Sierpinskiego charakterystyczny, jakby podpisem).
Dodam, ze korzysta sie z pewnika wyboru.

******

Wlodzimierz Holsztynski

[Marcin Kysiak]

Post by Wlodzimierz Holsztynski

Post by Marcin Kysiak
\aleph_0 --> (\aleph_0)^2_2.
Jest to nieskończone twierdzenie Ramsey'a;

Po ludzku: Pomalujmy kazda pare {x y}
liczb naturalnych x y na bialo lub na czarno

Jeszcze bardziej po ludzku:

W nieskończonym zbiorze osób istnieje nieskończony podzbiór, w którym
albo każde dwie się znają, albo żadne dwie się nie znają :-)

Post by Wlodzimierz Holsztynski
Niech a(0) bedzie dowolna liczba naturalna.
Nieskonczenie wiele krawedzi o koncu w a(0)
jest tego samego koloru, powiedzmy ze czarnego
(nie wykluczone, ze bialych krawedzi o koncu
w punkcie a(0) tez jest nieskonczenie wiele,
ale to nas nie obchodzi).
Budujmy, krok po kroku, poki to mozliwe, ciag
punktow a(k) i nieskonczonych zbiorow liczb
a(0) A(0) ... a(n) A(n) ...
takich, ze kazdy zbior A(k) zawiera sie w poprzednim,
podobnie a(k) \in A(k-1) dla k=1 2 ..., oraz kazda
para {a(k) y} jest pomalowana na czarno dla kazdego
y \in A(k), k=0 1 ...

Jak ktoś woli, to można to powiedzieć troszkę inaczej. Zamiast w
przedostatniej linijce mówić "na czarno", można powiedzieć "na ten sam
kolor". A na zakończenie zauważyć, że albo dla niesk. wielu k był to
kolor czarny, albo biały. Jako zbiór jednorodny bierzemy właśnie ten
nieskończony.

To teraz ambitniej: załóżmy, że \kappa jest liczbą kardynalną mierzalną
(tzn. istnieje uniwersalna miara dwuwartościowa \mu:P(\kappa)-->{0,1}
znikająca na punktach i \kappa-addytywna). Wykazać, że \kappa jest słabo
zwarta, tzn:

\kappa --> (\kappa)^2_2.

Jeszcze z tej beczki, bardzo mocne i dobre twierdzenie o kolorowaniach z
zeszłego roku chyba:

Istnieje kolorowanie par elementów zbioru X mocy \aleph_1 na \aleph_1
kolorów takie, że dla dowolnych podzbiorów A,B\subset X mocy
\aleph_1 każdy kolor jest przyjmowany dla pewnej pary {a,b}, gdzie a\in
A, b\in B.

Udowodnił to Justin T. Moore, a wnioskiem z tego jest rozwiązanie
pewnego problemu w topologii ogólnej dot. L-przestrzeni. Podobno (nie
mnie to oceniać) jeden z najlepszych wyników w teorii mnogości ostatnich
lat.

Pozdrawiam
Marcin

[Marcin Kysiak]

Post by Marcin Kysiak
Jak ktoś woli, to można to powiedzieć troszkę inaczej. Zamiast w
przedostatniej linijce mówić "na czarno", można powiedzieć "na ten sam
kolor". A na zakończenie zauważyć, że albo dla niesk. wielu k był to
kolor czarny, albo biały. Jako zbiór jednorodny bierzemy właśnie ten
nieskończony.

...tzn. zbiór tych k\in N, że mieliśmy A(k) tego koloru, który powtórzył
się nieskończenie wiele razy.

Pzdr,
M.