Nierówność z liczbą Ramseya

[pasjonat_matematyki]

Dzień dobry
Czy mogłabyś/mógłbyś mi udzielić wskazówki w tym zadaniu?
\(\displaystyle{ R(n+1,3) \ge 3n}\), gdzie lewa strona to liczba Ramseya.
Rozważyłem graf pełny \(\displaystyle{ K _{ 3n-1}}\) o wierzchołkach ponumerowanych \(\displaystyle{ \{1,2,3,...,3n-1\}}\) i pokolorowałem krawędzie \(\displaystyle{ {i,j}}\) następująco: na czerwono, jeśli \(\displaystyle{ |i-j|\equiv 1 \pmod{3}}\) i na niebiesko w przeciwnym wypadku. Łatwo pokazać, że przy takim kolorowaniu nie znajdziemy trójkąta czerwonego. Natomiast nie wiem co dalej. Czy trzeba z kolei rozważyć jakiś podgraf pełny tego grafu o wszystkich krawędziach niebieskich? I co z nim dalej? Ma on jakieś ograniczenie co do liczby wierzchołków? Nie wiem jak zliczyć te wierzchołki.

[arek1357]

Jest takie twierdzenie szacujące liczby Ramseya a mianowicie:

\(\displaystyle{ (r-1)(g-1)+1 \le R(r,g)=R(g,r) \le {r+g-2 \choose r-1} }\)

[a4karo]

Jest takie twierdzenie szacujące liczby Ramseya a mianowicie:

\(\displaystyle{ (r-1)(g-1)+1 \le R(r,g)=R(g,r) \le {r+g-2 \choose r-1} }\)

A sprawdziłeś czy tu się przyda, czy po prostu ciągnie Cię do pisania postów?

[arek1357]

Ciągnie mnie do pisania postów...

Dodano po 3 godzinach 43 minutach 35 sekundach:
A potrafisz to udowodnić dla:

\(\displaystyle{ R(4,3)>8}\) ?...

Tzn. narysować?

[a4karo]

Ja już jestem na etapie, że wiem gdzie szukać

Kod: Zaznacz cały

https://www.cut-the-knot.org/arithmetic/combinatorics/Ramsey43.shtml