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>. }}
Часто определение для чисел Рамсея дается через задачу "о друзьях и незнакомцах"<ref>[https://en.wikipedia.org/wiki/Theorem_on_friends_and_strangers|Theorem on friends and strangers]</ref>. Пусть на вечеринке каждые два человека могут быть либо друзьями, либо незнакомцами, какое минимальное количество людей должно присутствовать на празднике, чтобы хотя бы <tex>m<\/tex> человек были друзьями, или хотя бы <tex>n<\/tex> человек не будут знать друг друга. Если мы переформулируем данную задачу в терминах графов, то как раз получим определение числа Рамсея <tex>r(m, n)</tex>. Чтобы получить лучшее представление природы чисел Рамсея, приведем пример. Докажем, что <tex>r(3,3) = 6</tex>.
===Теорема Рамсея. Оценки сверху===
