Изменения

Перейти к: навигация, поиск

Теория Рамсея

81 байт убрано, 21:25, 29 ноября 2018
м
Числа Рамсея больших размерностей
|id=def5
|definition=
Пусть <tex>m,k,n_1,...,n_k \in \mathbb N</tex>, причём <tex>n_1,...,n_k \ge m</tex>. Число Рамсея <tex>r_m(k; n_1,...,n_k)</tex> — наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске <tex>m</tex>-элементных подмножеств <tex>x</tex>-элементного множества <tex>M</tex> в <tex>k</tex> цветов для некоторого <tex>i \in [1..k]</tex> обязательно найдётся такое множество <tex>W_i</tex>, что <tex>|W_i|=n_i</tex> и все <tex>m</tex>-элементные подмножества множества <tex>W_i</tex> имеют цвет <tex>i</tex>.}}{{Определение|id=def6|definition=Число <tex>m</tex> называется называют размерностью числа Рамсея <tex>r_m(k;n_1,...,n_k)</tex>.}}{{Утверждение|id=u4|about=4|statement=1) Нетрудно понять что числа Рамсея размерности 2 — это определённые выше числа Рамсея для клик<br>2) При количестве цветов, равном 2, этот параметр мы будем опускать и писать <tex>r_m(n_1,n_2)</tex> вместо <tex>r_m(2;n_1,n_2)</tex>.
}}
 
Нетрудно понять что числа Рамсея размерности <tex>2</tex> — это определённые выше числа Рамсея для клик.
 
При количестве цветов, равном <tex>2</tex>, этот параметр в записи обычно опускают и пишут <tex>r_m(n_1,n_2)</tex> вместо <tex>r_m(2;n_1,n_2)</tex>.
 
{{Определение
|id=def7|definition=
442
правки

Навигация