Теорія Ремзі

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

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

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

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

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

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

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

Шаблон:Докладніше Сам Ремзі довів таку теорему:

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

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

Мінімальне число $R$, за якого для заданого набору аргументів $a_1,a_2,\dots ,a_n$ існує зазначене в теоремі розфарбування, називається числом Ремзі. Питання про значення чисел Ремзі за невеликим винятком залишається відкритим.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Цю Шаблон:Нп довів 2003 року Шаблон:Iw.

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

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

Див. також

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

Література

• Шаблон:Книга-ру

Посилання

• Теорія Ремзі Шаблон:Ref-ru Шаблон:Webarchive