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

Теорія Ремзі — розділ математики, який вивчає умови, за яких у довільно сформованих математичних об'єктах зобов'язаний з'явитися певний порядок. Названа на честь Френка Ремзі.

Завдання теорії Ремзі зазвичай звучать у формі питання «скільки елементів має бути в деякому об'єкті, щоб гарантовано виконувалося задана умова чи існувала задана структура?». Найпростіший приклад:

• Довести, що в будь-якій групі з 6 осіб, знайдуться троє людей, знайомих одне з одним, або троє людей, попарно незнайомих одне з одним.

Класичні результати

Припустимо, наприклад, що ми знаємо, що ${\displaystyle n}$ кроликів розсаджено в ${\displaystyle m}$ кліток. Наскільки великим має бути ${\displaystyle n}$щоб гарантовано в одній з кліток було принаймні 2 кроликів? Згідно з принципом Діріхле, якщо ${\displaystyle n>m}$, то знайдеться клітка, в якій буде мінімум 2 кроликів. Теорія Ремзі узагальнює цей принцип.

Огляд результатів до 1990 р. дано в роботі.

Теорема Ремзі

Докладніше: Теорема Ремзі

Сам Ремзі довів таку теорему:

Нехай дано числа ${\displaystyle a_{1},\;a_{2},\;\ldots ,\;a_{n}}$. Тоді існує таке число ${\displaystyle R}$, що, як би ми не пофарбували ребра повного графу на ${\displaystyle R}$ вершинах у ${\displaystyle n}$ кольорів, знайдеться або повний підграф 1-го кольору на ${\displaystyle a_{1}}$ вершинах, або повний підграф 2-го кольору на ${\displaystyle a_{2}}$ вершинах, … або повний підграф ${\displaystyle n}$-го кольору на ${\displaystyle a_{n}}$ вершинах.

Її було узагальнено на випадок гіперграфу.

Мінімальне число ${\displaystyle R}$, за якого для заданого набору аргументів ${\displaystyle a_{1},\;a_{2},\;\ldots ,\;a_{n}}$ існує зазначене в теоремі розфарбування, називається числом Ремзі. Питання про значення чисел Ремзі за невеликим винятком залишається відкритим.

Теорема ван дер Вардена

Схожа за формулюванням, але відрізняється доведенням теорема ван дер Вардена:

Для кожного набору чисел ${\displaystyle a_{1},\;a_{2},\;\ldots ,\;a_{n}}$ існує таке число ${\displaystyle W}$, що, як би ми не пофарбували перші ${\displaystyle W}$ натуральних чисел ${\displaystyle n}$ кольорів, знайдеться або арифметична прогресія 1-го кольору довжини ${\displaystyle a_{1}}$, або арифметична прогресія 2-го кольору довжини ${\displaystyle a_{2}}$, …, або арифметична прогресія ${\displaystyle n}$-го кольору довжини ${\displaystyle a_{n}}$.

Найменше таке число називається числом ван дер Вардена.

Замість множини натуральних чисел можна розглянути ґратку ${\displaystyle \mathbb {Z} ^{n}}$, а арифметичних прогресій — фігури в ній, гомотетичні даній, і твердження теореми залишиться правильним (узагальнена теорема ван дер Вардена).

Теорема Хейлса — Джеветта

Для будь-яких чисел ${\displaystyle n}$ і ${\displaystyle c}$ можна знайти число ${\displaystyle H}$ таке, що якщо комірки ${\displaystyle H}$-вимірного куба зі стороною довжини ${\displaystyle n}$ розфарбовано в ${\displaystyle c}$ кольорів, то існує хоча б одна лінія (лінією вважаються рядки, стовпці, деякі діагоналі) з ${\displaystyle n}$ одноколірних комірок.

З цієї теореми випливає, що під час гри в багатовимірні хрестики-нулики при будь-якій довжині рядка та будь-якому числі гравців можна знайти таке число вимірів, що нічия буде неможлива.

Гіпотеза Ердеша — Секереша про опуклі багатокутники

Для будь-якого натурального ${\displaystyle N}$, кожна достатньо велика множина точок у загальному положенні на площині має підмножину з ${\displaystyle N}$ точок, які є вершинами опуклого багатокутника.

Згідно з гіпотезою Ердеша та Секереша про опуклі багатокутники число точок в загальному положенні, у яких обов'язково існує опуклий ${\displaystyle N}$-кутник задається формулою:

${\displaystyle f(N)=1+2^{N-2}}$ для всіх ${\displaystyle N}$

Вони ж довели, що у множині з меншим числом точок опуклий ${\displaystyle N}$-кутник може не існувати.

Теорема Крута про одноколірний єгипетський дріб

Для будь-якої розмальовки цілих чисел більших від ${\displaystyle 1}$ в ${\displaystyle r>0}$ кольорів існує скінченна одноколірна підмножина ${\displaystyle S}$ цілих така, що ${\displaystyle \sum _{n\in S}1/n=1.}$ При цьому максимальний елемент, а отже й розмір множини ${\displaystyle S}$ обмежений показниковою функцією від ${\displaystyle r}$ зі сталою основою.

Цю ^[ru] довів 2003 року ^[en].

Особливості теорії

Для результатів у рамках теорії Ремзі характерні дві властивості. По-перше, вони неконструктивні. Доводиться, що деяка структура існує, але не пропонується жодного способу її побудови, окрім прямого перебору. По-друге, щоби шукані структури існували, потрібно, щоб об'єкти, які їх містять, складалися з дуже великого числа елементів. Залежність числа елементів об'єкта від розміру структури зазвичай, принаймні, експоненціальна.

Див. також

• Гіпотеза Ердеша — Бура

Примітки

1. Graham, R.; Rothschild, B.; (1990), Ramsey Theory (вид. 2nd), New York: John Wiley and Sons, ISBN .
2. Ramsey, F. P. (1930), On a problem of formal logic, Proc. London Math. Soc. Series 2, 30: 264—286, doi:10.1112/plms/s2-30.1.264
3. van der Waerden, B. L. (1927). Beweis einer Baudetschen Vermutung. Nieuw. Arch. Wisk. 15: 212—216.
4. Hales A., Jewett R. Regularity and positional games // Trans. Amer. Math. Soc. 106 (1963), p. 222—229.
5. Erdős, P.; Szekeres, G. (1935), , Compositio Math, 2: 463—470, архів оригіналу за 19 лютого 2019, процитовано 18 лютого 2019

Література

• Мартин Гарднер. Глава 17. Теория Рамсея // От мозаик Пенроуза к надёжным шифрам = Penrose Tiles to Trapdoor Ciphers / пер. с англ. Ю. А. Данилова. — М. : Мир, 1993. — С. 288—308. — 416 с. — 10 000 екз. — .

Посилання

• Теорія Ремзі (рос.) [ 19 лютого 2019 у Wayback Machine.]