Рамсея теорема

- название нескольких теорем в дискретной математике, сформулированных и доказанных Ф. Рамсеем [1]. Первую из этих теорем Ф. Рамсей сформулировал следующим образом. Пусть Г- бесконечный класс и m и r - положительные целые числа; и пусть все те подклассы Г, к-рые имеют r элементов или, иначе, все r-сочетания элементов Г, разделены любым способом на m, взаимно исключающих классов С i, i=1, 2,..., m, так, что каждое r-сочетание является элементом одного и только одного класса С i;тогда, предполагая справедливой аксиому выбора, класс Г должен содержать бесконечный подкласс D такой, что все r-сочетания членов D принадлежат одному и тому же классу С i. К о н е ч н ы й а н а л о г этой Р. т., также установленный Ф. Рамсеем, можно сформулировать следующим образом. Пусть S - множество, с. Последнюю теорему можно пояснить примером, в к-ром вычисляется число п(3, 3, 2). Рассматриваются шесть точек на плоскости, связанных попарно дугами, каждая из к-рых окрашена либо в красный, либо в голубой цвета. Существуют три точки такие, что дуги, соединяющие их, окрашены в один и тот же цвет. Из пяти дуг, соединяющих нек-рую точку Р 0 с пятью другими точками, три дуги одного цвета (напр., красного). Пусть это дуги [img: http://localhost:8080/file/041865-126.jpg]. Если какая-нибудь из дуг [img: http://localhost:8080/file/041865-127.jpg] красная, то она и две другие, соединяющие ее концы с точкой Р 0, образуют красный треугольник, если же они все голубые, то сами образуют голубой треугольник. Это означает, что [img: http://localhost:8080/file/041865-128.jpg] [img: http://localhost:8080/file/041865-129.jpg]. Однако пять точек на плоскости можно так попарно соединить красными и голубыми дугами, что при этом не найдется треугольника одного цвета. Для этого пусть дуги [img: http://localhost:8080/file/041865-130.jpg] будут красными, а остальные - голубыми. Это показывает, что n(3, 3, 2)>5. Таким образом, n(3, 3, 2) = 6. Из Р. т. вытекает следующий результат: для данного натурального [img: http://localhost:8080/file/041865-131.jpg] существует целое число N=N(n).такое, что любые Nточек в плоскости, никакие три из к-рых не лежат на одной прямой, содержат пточек, образующих выпуклый n-угольник (см. [4]).