Matematyka.pl

Wykazać, że dla każdego k istnieje takie N, że przy dowolnym kolorowaniu boków i przekątnych N-kąta foremnego dwoma kolorami musi istnieć k wierzchołków takich, że wszystkie odcinki pomiędzy nimi są tego samego koloru.

Kolory niebieski, czerwony.

Klika (o \(\displaystyle{ n}\) wierzcholkach) = pelny graf (o \(\displaystyle{ n}\) wierzcholkach).

Na poczatek takie spostrzezenie:

Lemat. Niech zbior \(\displaystyle{ X}\) ma \(\displaystyle{ n > 0}\) elementow, zbiory \(\displaystyle{ X_1,...,X_t}\) beda pewnymi podzbiorami zbioru \(\displaystyle{ X}\),
zas zbiory \(\displaystyle{ X_1',...,X_t'}\) ich dopelnieniami odpowiednio. Istnieja wowczas zbiory \(\displaystyle{ Y_1,...,Y_t}\), takie,
ze \(\displaystyle{ Y_i=X_i}\) lub \(\displaystyle{ Y_i=X_i'}\) oraz \(\displaystyle{ \bigcap Y_i}\) ma przynajmniej \(\displaystyle{ \frac{n}{2^t}}\) elementow.



Dowod lematu: Zauwazmy, ze jesli \(\displaystyle{ A,B}\) sa dowolnymi podzbiorami w \(\displaystyle{ X}\), to jeden ze zbiorow \(\displaystyle{ A\cap B}\) lub \(\displaystyle{ A\cap B'}\)
zawiera przynajmniej polowe elementow zbioru \(\displaystyle{ A}\). Ponadto jeden ze zbiorow \(\displaystyle{ X_1}\) lub \(\displaystyle{ X_1'}\) ma
przynajmnniej \(\displaystyle{ \frac{n}{2}}\) elementow. Przecinajac kolejno ten zbior z pozostalymi lub
ich dopelnieniami dbajac o to, zeby w przecieciu zawsze w przecieciu zostawala polowa
elementow otrzymamy ostatecznie zbior majacy przynajmniej
\(\displaystyle{ \frac{n}{2^t}}\) elementow.

Teraz do zadania.
Dowod przez indukcje. Dla \(\displaystyle{ k = 2}\) jest jasne. Ciekawostka: dla \(\displaystyle{ k=3}\) wystarczy
\(\displaystyle{ n=6}\).

Przypuscmy, ze mamy pokazane dla pewnego \(\displaystyle{ k>0}\), to jest znalezlismy takie
\(\displaystyle{ n_k}\)ze kazdy graf pelny rozmiaru \(\displaystyle{ n}\), ktorego krawedzie pokolorowano
dwoma kolorami zawiera klike rozmiaru \(\displaystyle{ k}\) ktorej krawedzie sa jednobarwne.

Pokazemy dla \(\displaystyle{ k+1}\).

Niech \(\displaystyle{ X}\) bedzie grafem pelnym rozmiaru \(\displaystyle{ N_0}\) o wierzcholkach \(\displaystyle{ \{x_1,...,x_N\}}\)
ktorego krawedzie pokolorowano dwoma kolorami.

Kazdy wierzcholek tego grafu wyznacza zbior wierzcholkow polaczonych z nim niebieska krawedzia.
Oznaczmy zbiory tak wyznaczone, odpowiadajace wierzcholkom \(\displaystyle{ x_1,...,x_{N_0}}\) odpowiednio
\(\displaystyle{ X_1,...,X_{N_0}}\).

Na mocy lematu, dla kazdego \(\displaystyle{ t\in \mathbb{N}}\) istnieja takie zbiory \(\displaystyle{ Y_1,...,Y_t}\), ze \(\displaystyle{ Y_i=X_i}\)
lub \(\displaystyle{ Y_i=X_i'}\) oraz \(\displaystyle{ Y=\bigcap Y_i}\) ma przynajmniej \(\displaystyle{ \frac{N_0}{2^t}}\) elementow. Dla odpowiednio
duzego \(\displaystyle{ N_0}\) (z zalozenia indukcyjnego dla \(\displaystyle{ N_0 \geqslant 2^t n_k}\)) w podgrafie, ktorego wierzcholki to zbior
\(\displaystyle{ Y}\), istnieje klika rozmiaru \(\displaystyle{ k}\), oznaczmy ja \(\displaystyle{ Q_1}\), ktorej krawedzie sa wspolbarwne, powiedzmy
niebieskie.

Jesli \(\displaystyle{ t>n_k}\) (do istnienia takiego \(\displaystyle{ t}\) wystarczy, ze \(\displaystyle{ N_0>n_k}\)), to w podgrafie o wierzcholkach
\(\displaystyle{ x_1,...,x_{N_0}}\) na mocy zalozenia indukcyjnego istnieje klika rozmiaru \(\displaystyle{ k}\) o jednobarwnych
krawedziach, nazwijmy ja \(\displaystyle{ Q_2}\). Z konstrukcji wynika, ze zbiory \(\displaystyle{ Q_1}\) i \(\displaystyle{ Q_2}\) sa rozlaczne, bo dla
kazdego \(\displaystyle{ i=1,2,...,t}\) \(\displaystyle{ x_i}\) nie nalezy do \(\displaystyle{ Y_i}\). Niech wierzcholkami \(\displaystyle{ Q_2}\) beda \(\displaystyle{ q_1,...,q_k}\).
Na mocy konstrukcji, dla kazdego \(\displaystyle{ i=1,...,t}\) wszystkie krawedzie laczace wierzcholek \(\displaystyle{ x_i}\) z
wierzcholkami \(\displaystyle{ Q_1}\) sa jednobarwne. Dotyczy to wiec rowniez wierzcholkow grafu \(\displaystyle{ Q_2}\).
Gdyby dla pewnego \(\displaystyle{ q\in Q_2}\) te krawedzie byly niebieskie, to \(\displaystyle{ Q_2 + q}\) tworzyloby klike
rozmiaru \(\displaystyle{ k+1}\) i mamy krok indukcyjny.

Zalozmy wiec, ze dla kazdego \(\displaystyle{ q\in Q_2}\) wszystkie krawedzie laczace \(\displaystyle{ q}\) z wierzcholkami \(\displaystyle{ Q_1}\) sa
czerwone. Otrzymalismy wiec nastepujacy fakt:

Dla odpowiednio duzego \(\displaystyle{ N_0}\) w grafie pelnym o \(\displaystyle{ N_0}\) wierzcholkach
(A) mozna znalezc graf pelny rozmiaru \(\displaystyle{ k+1}\) o jednobarwnych krawedziach
lub
(B) 2 rozlaczne jednobarwne kilki rozmiaru \(\displaystyle{ k}\) takie, ze wszystkie krawedzie laczace wierzcholki
roznych klik sa jednobarwne drugiego koloru.

Powtarzajac identyczny argument otrzymujemy nastepujacy fakt:

Dla odpowiednio duzego \(\displaystyle{ N_1}\) w grafie pelnym o \(\displaystyle{ N_1}\) wierzcholkach
(A) mozna znalezc graf pelny rozmiaru \(\displaystyle{ k+1}\) o jednobarwnych krawedziach
lub
(B) 3 rozlaczne jednobarwne kilki rozmiaru \(\displaystyle{ k}\) takie, ze wszystkie krawedzie laczace wierzcholki
tych roznych klik sa jednobarwne drugiego koloru.

Dokladniej. Wybieramy tak duze \(\displaystyle{ N_1}\), ze przeciecie \(\displaystyle{ t=n_k}\) podzbiorow zbioru \(\displaystyle{ N_1}\) elementowych
lub ich dopelnien ma przynajmniej \(\displaystyle{ N_0}\) elementow. Skad powtarzajac identyczny argument
otrzymujemy 3 rozlaczne jednobarwne kliki polaczone parami krawedziami drugiego koloru.

W ten sam sposob konstrujemy liczby \(\displaystyle{ N_2,...,N_{k+1}}\), czyli otrzymujemy fakt:

Dla odpowiednio duzego \(\displaystyle{ N_{k+1}}\) w grafie pelnym o \(\displaystyle{ N_{k+1}}\) wierzcholkach
(A) mozna znalezc graf pelny rozmiaru \(\displaystyle{ k+1}\) o jednobarwnych krawedziach
lub
(B) \(\displaystyle{ k+1}\) rozlacznych jednobarwnych kilk rozmiaru \(\displaystyle{ k}\) takie, ze wszystkie krawedzie laczace wierzcholki
roznych klik sa jednobarwne drugiego koloru.

Jesli w powyzszym zachodzi przypadek (B), to wybierajac po jednym wierzcholku z kazdej z tych \(\displaystyle{ k+1}\)
klik otrzymujemy klike \(\displaystyle{ k+1}\) elementowa w "drugim" kolorze. Otrzymalismy wiec fakt:

W grafie pelnym o \(\displaystyle{ N_{k+1}}\) wierzcholkach istnieje jednobarwna klika rozmiaru \(\displaystyle{ k+1}\).

Krok indukcyjny jest wiec zakonczony, chociaz wielkosc grafu wynikajaca z tego argumentu jest
raczej nieoptymalna (rzad wielkosci \(\displaystyle{ N}\) to mniej wiecej \(\displaystyle{ 2^{(k!)^2}}\)). N rzedu \(\displaystyle{ 2^{k+3}}\) powinno
wystarczyc, ale nie umiem na to podac dowodu.

Mozna takze (trzeba?!) powiedziec iz tw wynika z teorii Ramseya. Zachodzi np:
Niech \(\displaystyle{ r, g q 2}\) i \(\displaystyle{ n= {r+g-2 \choose r-1}}\) Wtedy jesli krawedzie grafu pełnego \(\displaystyle{ K_n}\) sa pokolorowane na zielono lub czerwono to istnieje czerwony podgraf \(\displaystyle{ K_r}\) albo zielony podgraf \(\displaystyle{ K_g}\)

*\(\displaystyle{ K_n}\) to graf o n wierzchołkachgdzie kazda para polaczona jest krawedzia.
W zadaniu Mozna wziasc np g=r, i mamy liczbe n

**Liczbe Ramseya \(\displaystyle{ R(r,g)}\) definiuje sie jako najmniejsze n o takiej własnosci jak w powyzszym twierdzeniu.

Tutaj lepiej pasuje twierdzenie Turana niż liczby Ramsey'a.

Mruczek pisze:Tutaj lepiej pasuje twierdzenie Turana niż liczby Ramsey'a.

To dla Ciebie:
A twierdzenie Ramseya tutaj jak najbardziej pasuje.
Swoją drogą istnieje bardzo fajny i krótki dowód używający metody probabilistycznej.

Ok, rzeczywiście.

Z tą metodą probabilistyczną chodziło Ci o taki dowód jak np. ten z rozdziału 3.1 stąd:

?