Liczby Ramseya. Nierówność.

[pasjonat_matematyki]

Dzień dobry

Zastanawiam się, dlaczego \(\displaystyle{ R(m _{1}, m _{2}, m _{3}) \le R(m _{1}, R(m _{2}, m _{3}))}\).
Czyli minimalny graf pokolorowany trzema kolorami mający przynajmniej jeden monochromatyczny podgraf nie może być większy niż minimalny graf mający podgraf w kolorze \(\displaystyle{ 1}\) lub minimalny podgraf dla kolorów \(\displaystyle{ 2}\) lub \(\displaystyle{ 3}\). Jak można by to uzasadnić?

[arek1357]

Weź graf pełny rozpięty na wierzchołkach:

\(\displaystyle{ R(m_{1},R(m_{2},m_{3}))}\)

I pokoloruj go trzema kolorami:1,2,3, potem kolory 2 i 3 potraktuj jako jeden kolor, wtedy masz monochromatyczną klikę:

\(\displaystyle{ m_{1}}\) lub dwukolorową (jednokolorową) klikę: \(\displaystyle{ m_{2} \vee m_{3}}\)

Czyli prawa strona nierówności może zawierać monochromatyczne kliki:

\(\displaystyle{ m_{1}, m_{2}, m_{3}}\)

Czyli nierówność prawdziwa...

To tak trzeba sobie to jakoś poukładać w głowie... bo w takich przypadkach trudno o naprawdę dobrą formę przekazu...

Cała idea polega na tym, że najpierw dwa kolory utożsamiamy a potem je rozdzielamy i w ten sposób wykazujemy, że kliki takie mogą istnieć...

[pasjonat_matematyki]

Czyli to wygląda na zadanie z logiki. Graf mający klikę \(\displaystyle{ m _{1}}\) lub podgraf z kliką \(\displaystyle{ m _{2}}\) lub \(\displaystyle{ m _{2}}\) musi mieć kliki \(\displaystyle{ m _{1}}\) lub \(\displaystyle{ m _{2}}\) lub \(\displaystyle{ m _{3}}\) .
Czy dla przypadku \(\displaystyle{ k}\) też można przeprowadzić takie rozumowanie?
\(\displaystyle{ R(m _{1}, m _{2}, ..., m _{k}) \le R(m _{1}, R(m _{2},...,m _{k}))}\) Czy indukcja jest niepotrzebna? A jeśli jest, to jak by wyglądało przejście indukcyjne?

[arek1357]

Według mnie przejście na indukcję byłoby:

\(\displaystyle{ R(m_{1},m_{2},...,m_{k}) \le R((m_{1},m_{2},...,m_{k-2},R(m_{k-1},m_{k}))}\)

[pasjonat_matematyki]

Znalazłem coś takiego, gdzie ogólna nierówność jest właśnie w tej postaci, którą podałem:

Kod: Zaznacz cały

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

Ale mój angielski jest słaby. Rozumiesz o co im tam chodzi?

[arek1357]

Jest tam przedstawione analogiczne rozumowanie, najpierw kolorujesz na kilka kolorów, potem nie dwa tylko n-1 kolorów utożsamiasz ...

Nic specjalnie ciekawego w tym nie ma...