Liczby Ramseya

[niewiemcosiedzieje]

Dzień dobry,

Mam problem z zadaniem i poprosiłbym o pomoc i możliwe wskazówki.
Oto treść zadania:

Zakładając, że obie liczby Ramseya \(\displaystyle{ R(n−1, m)}\) oraz \(\displaystyle{ R(n, m−1)}\) są parzyste, uzasadnić nierówność:
\(\displaystyle{ R(n, m) < R(n − 1, m) + R(n, m − 1)}\)

Nie wiem czy dobrze zrozumiałem liczby Ramseya, więc pozwolę sobie przedstawić moje rozumowanie.
Mając przykładowo \(\displaystyle{ R(3,3)}\) mamy 3 krawędzie koloru czerwonego i 3 krawędzie koloru niebieskiego. Musimy znaleźć graf pełny o takiej liczbie wierzchołków, dla której przy dowolnym kolorowaniu krawędzi znajdziemy klikę, która będzie monochromatyczna.
Proszę mnie poprawić, jeśli źle to zrozumiałem.
Z góry dziękuję za pomoc.

[janusz47]

Tak. Niech dane będzie pewne pokolorowanie krawędzi pełnego \(\displaystyle{ 6- }\) grafu. Rozpatrzmy dowolny wierzchołek na przykład \(\displaystyle{ W_{0}. }\) Co najmniej trzy z pięciu krawędzi wychodzących z tego wierzchołka mają ten sam kolor. Załóżmy, że krawędzie \(\displaystyle{ W_{0}W_{1}, W_{0}W_{2}, W_{0}W_{3}}\) są niebieskie, Jeśli jedna z krawędzi \(\displaystyle{ W_{1}W_{2}, W_{1}W_{3}, W_{2}W_{3}, }\) na przykład \(\displaystyle{ W_{1}W_{2} }\) jest niebieska, to \(\displaystyle{ 3- }\) graf o wierzchołkach \(\displaystyle{ ] W_{0}, W_{1}, W{2} }\) jest monochromatyczny, w przeciwnym przypadku \(\displaystyle{ 3-}\) graf o wierzchołkach \(\displaystyle{ W_{1}, W_{2},W_{3} }\) jest monochromatyczny czerwony.

Udowodniliśmy, że dla każdego pokolorowania na dwa kolory pełny \(\displaystyle{ 6-}\) graf ma monochromatyczny \(\displaystyle{ 3- }\) podraf.

Z lematu tego wynika, że liczba Ramseya \(\displaystyle{ R(3,3) = 6. }\)

Niech \(\displaystyle{ R(n-1),m) = 2p, \ \ R(n, m-1) = 2q, \ \ p,q \in \NN. }\)

Niech \(\displaystyle{ n = 2p + 2q -1 }\), niech \(\displaystyle{ W }\) będzie dowolnym wierzchołkiem pełnego \(\displaystyle{ n- }\) grafu, \(\displaystyle{ n_{1}- }\) liczbą czerwonych krawędzi wychodzących z \(\displaystyle{ W,}\). Wtedy prawdziwa jest równość

\(\displaystyle{ n-1 = n_{1}+n_{2} = R(n-1), m) + R(n,m-1) -2 }\)

Rozpatrz trzy przypadki:

\(\displaystyle{ 1) \ \ n_{1}\geq R(n-1, m), \ \ n_{2} < R(n, m-1) }\)

\(\displaystyle{ 2) \ \ n_{2} \geq R(n, m-1), \ \ n_{1}< R(n-1, m) }\)

\(\displaystyle{ 3) \ \ n_{1} = 2p -1,\ \ n_{2} = 2q-1. }\)

Pierwsze dwa przypadki - indukcja matematyczna dla liczby krawędzi \(\displaystyle{ s = n +m, \ \ s\geq 6. }\)

Jeśli dla wszystkich wierzchołków zachodzi trzeci przypadek, to liczba końców krawędzi czerwonych jest równa

\(\displaystyle{ (2p+2q-1)(2p-1) }\) co jest niemożliwe, bo liczba ta musi być parzysta.

[niewiemcosiedzieje]

Dziękuję Panu za odpowiedź. Mam kilka pytań. Prosiłbym o odpowiedzenie w ramach możliwości.

Niech \(\displaystyle{ R(n-1),m) = 2p, \ \ R(n, m-1) = 2q, \ \ p,q \in \NN. }\)

Ten fragment rozumiem. Obie liczby są parzyste. Dlatego 2p i 2q.

Niech \(\displaystyle{ n = 2p + 2q -1 }\), niech \(\displaystyle{ W }\) będzie dowolnym wierzchołkiem pełnego \(\displaystyle{ n- }\) grafu, \(\displaystyle{ n_{1}- }\) liczbą czerwonych krawędzi wychodzących z \(\displaystyle{ W,}\). Wtedy prawdziwa jest równość

Tego nie rozumiem. Dlaczego liczba wierzchołków danego grafu jest zależna od sumy tych dwóch liczb - 1?

\(\displaystyle{ n-1 = n_{1}+n_{2} = R(n-1), m) + R(n,m-1) -2 }\)

Liczba wierzchołków danego grafu pełnego jest taka sama jak liczba wychodzących z dowolnego wierzchołka krawędzi czerwonych (\(\displaystyle{ n_{1}- }\)) + krawędzi niebieskich (\(\displaystyle{ n_{2}- }\)) + 1, aby uwzględnić wierzchołek z którego te krawędzie wychodzą. Jednak znów: dlaczego to jest równe \(\displaystyle{ R(n-1), m) + R(n,m-1) -2 }\) ?

Rozpatrz trzy przypadki:

\(\displaystyle{ 1) \ \ n_{1}\geq R(n-1, m), \ \ n_{2} < R(n, m-1) }\)

\(\displaystyle{ 2) \ \ n_{2} \geq R(n, m-1), \ \ n_{1}< R(n-1, m) }\)

\(\displaystyle{ 3) \ \ n_{1} = 2p -1,\ \ n_{2} = 2q-1. }\)

Trzeci przypadek chyba rozumiem. Liczba krawędzi wychodzących jest zależna od ilości wierzchołków (bo w grafie pełnym z dowolnego wierzchołka wychodzi krawędź do każdego innego wierzchołka), a -1, aby uwzględnić wierzchołek z którego te krawędzi "zaczynamy" prowadzić. Jednak nie rozumiem przypadku 1 i 2.

Pierwsze dwa przypadki - indukcja matematyczna dla liczby krawędzi \(\displaystyle{ s = n + m, \ \ s\geq 6. }\)

Jakie wartości może przyjmować n i m?

Jeśli dla wszystkich wierzchołków zachodzi trzeci przypadek, to liczba końców krawędzi czerwonych jest równa

\(\displaystyle{ (2p+2q-1)(2p-1) }\) co jest niemożliwe, bo liczba ta musi być parzysta.

Skąd to mnożenie?

Przepraszam za problem i za masę pytań. Proszę o wyrozumiałość.

[janusz47]

" nie rozumiem przypadków 1), 2)"

Z własności liczb Ramsey'a

\(\displaystyle{ R(2,m) = m, \ \ R(n, 2) = n }\)

Jeśli \(\displaystyle{ n = m = 3 }\), to \(\displaystyle{ 6 = R(3,3 )\leq R(3,2) + R(2,3)= 3 + 3. }\)

Zaółóżmy , że udowodniono, iż liczby \(\displaystyle{ R(n-1),m), \ \ R(n, m-1) }\) istnieją. Rozważamy pełny \(\displaystyle{ n-}\) graf. którego krawędzie pomalowane są na dwa kolory (czerwony, niebieski).

Jeśli \(\displaystyle{ W }\) będzie dowolnym wierzchołkiem, \(\displaystyle{ T_{1} }\) - zbiorem wierzchołków połączonych z \(\displaystyle{ W }\) krawędzią czerwoną, \(\displaystyle{ T_{2} }\) - zbiorem wierzchołków połączonych z \(\displaystyle{ W }\) krawędzią niebieską i jeśli \(\displaystyle{ n_{1} = |T_{1}|, \ \ n_{2}= |T_{2}|, }\) wtedy prawdziwa jest równość na liczbę wszystkich wierzchołków

\(\displaystyle{ n = n_{1} + n_{2} +1 = R(n-1),m) + R(n,m-1) }\)

Stąd rozważamy dwa przypadki \(\displaystyle{ 1), 2). }\)

W pierwszym przypadku z definicji liczby \(\displaystyle{ R(n-1),m) }\) wynika, że w podgrafie \(\displaystyle{ T_{1} }\) znajdziemy albo monochromatyczny \(\displaystyle{ m- }\) podgraf niebieski, albo monochromatyczny \(\displaystyle{ n - 1 }\) podgraf czerwony.

W drugim przypadku, dołączając do monochromatycznego podgrafu czerwonego wierzchołolek \(\displaystyle{ W }\), otrzymamy monochromatyczny \(\displaystyle{ n -}\) podgraf czerwony.

W przypadku drugim postępujemy analogicznie.

Równość \(\displaystyle{ n = 2p+2q -1 }\) ze wzoru na liczbę wierzołków \(\displaystyle{ n -}\) grafu pełnego.

To mnożenie wynika ze wzoru na liczbę wierzchołków dwóch podgrafów pełnych o dwóch różnych kolorach.

Nie podoba mi się słowo "klik," dlatego używam pojęcia " podgraf pełny."

[niewiemcosiedzieje]

\(\displaystyle{ n = n_{1} + n_{2} +1 = R(n-1),m) + R(n,m-1) }\)

No i znów. Równość "\(\displaystyle{ n = n_{1} + n_{2} +1}\)" wydaję się, że rozumiem, ale dlaczego to jest równe \(\displaystyle{ R(n-1),m) + R(n,m-1)}\). Co mają wspólnego dwie liczby Ramseya, których wartości, to np. kolejno 18 i 25, do jednego grafu? W tym przypadku ten graf (z równania) miałby 43 wierzchołki. Nie rozumiem tego
Wydaję mi się, że jeśli zrozumiem tą kwestię, to automatycznie będę wiedział

Równość \(\displaystyle{ n = 2p+2q -1 }\) ze wzoru na liczbę wierzołków \(\displaystyle{ n -}\) grafu pełnego.

.
Przepraszam, ale nie jestem w stanie zrozumieć, co dwie liczby Ramseya opisujące dwa grafy o różnej ilości wierzchołków, mają wspólnego z grafem, który ma wierzchołków tyle, ile wynosi suma tych dwóch liczb.

[janusz47]

Jeszcze raz.
Załóżmy, że udowodniono iż liczby \(\displaystyle{ , R(n-1,m) \ \ R(n,m-1) }\) istnieją. Niech \(\displaystyle{ n = R(n-1, m) + R(n,m-1) }\) Rozważmy pełny \(\displaystyle{ n - }\) graf, którego krawędzie pomalowane są na dwa różne kolory np. kolor czerwony i kolor niebieski. Niech \(\displaystyle{ W }\) będzie dowolnym wierzchołkiem tego grafu.
\(\displaystyle{ T_{1}}\) zbiorem wierzchołków połączonych z \(\displaystyle{ W }\) - krawędziami czerwonymi. \(\displaystyle{ T_{2}}\) - zbiorem wierzchłków połączonych krawędziami niebieskimi. Niech liczności zbiorów zawierające te wierzchołki wynoszą odpowiednio \(\displaystyle{ |T_{1}|= n_{1}, \ \ |T_{2}| = n_{2}. }\)

Wtedy prawdziwa jest równość

\(\displaystyle{ n = n_{1} + n_{2} +1 = R(n-1), m) + R(n,m-1) }\)

W przypadku pierwszym (\(\displaystyle{ n_{1}\geq R(n-1,m), \ \ n_{2}< R(n,m-1))}\) z definicji liczby \(\displaystyle{ R(n-1,m)}\) wynika, że w podgrafie \(\displaystyle{ T_{1} }\) znajdziemy albo monochromatyczny \(\displaystyle{ m -}\) podgraf niebieski , albo monochromatyczny \(\displaystyle{ n-1 }\) podgraf
czerwony. Dołączając zaś do monochromatycznego podgrafu czerwonego wierzchołek \(\displaystyle{ W }\), otrzymamy monochromatyczny
\(\displaystyle{ n- }\) podgraf czerwony.
W drugim przypadku (\(\displaystyle{ n_{2} \geq R(n,m-1), \ \ n_{1}< R(n-1), m) }\) postępujemy analogicznie.

Dodano po 13 minutach 5 sekundach:
Niech \(\displaystyle{ n = 2p +2q -1 ... }\) to jest założenie.