442
правки
Изменения
→Существование. Оценки сверху
|definition='''Число Рамсея''' <tex>r(m, n)</tex> (англ. ''Ramsey's number'') {{---}} наименьшее из таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске ребер полного графа на <tex>x</tex> вершинах в два цвета найдется клика на <tex>n</tex> вершинах с ребрами цвета <tex>1</tex> или клика на <tex>m</tex> вершинах с ребрами цвета <tex>2</tex>. }}
===СуществованиеТеорема Рамсея. Оценки сверху==={{Теорема|id=ter1|about=1, Теорема Рамсея |statement=Для любых <tex>n,m \in \mathbb N</tex> существует число <tex>r(n,m)</tex>, при этом <tex>r(n,m) \le r(n,m-1)+r(n-1,m)</tex>, при этом а также если числа <tex>r(n,m-1)</tex> и <tex>r(n-1,m)</tex> четные, то неравенство принимает вид <tex>r(n,m) \le r(n,m-1)+r(n-1,m) - 1</tex> .
|proof=
