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

розділ математики

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

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

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

Класичні результатиРедагувати

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

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

Теорема РамсеяРедагувати

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

Нехай дано числа  . Тоді існує таке число  , що, як би ми не пофарбували ребра повного графа на   вершинах у   кольорів, знайдеться або повний підграф 1-го кольору на   вершинах, або повний підграф 2-го кольору на   вершинах, … або повний підграф  -го кольору на   вершинах.[2]

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

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

Теорема ван дер ВарденаРедагувати

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

Для кожного набору чисел   існує таке число  , що, як би ми не пофарбували перші   натуральних чисел   кольорів, знайдеться або арифметична прогресія 1-го кольору довжини  , або арифметична прогресія 2-го кольору довжини  , …, або арифметична прогресія  -го кольору довжини  .[3]

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

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

Теорема Хейлса — ДжеветтаРедагувати

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

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

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

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

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

  для всіх  

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

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

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

 

При цьому максимальний елемент, а отже й розмір множини   обмежений показниковою функцією від   з постійною основою.

Цю гіпотезу Ердеша — Грема[ru] доведено Ернестом Крутом[en] у 2003 році.

Особливості теоріїРедагувати

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

ПриміткиРедагувати

  1. Graham, R.; Rothschild, B.; Spencer, J. H. (1990). Ramsey Theory (вид. 2nd). New York: John Wiley and Sons. ISBN 0-471-50046-1. .
  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). A combinatorial problem in geometry. Compositio Math 2: 463–470. 

ЛітератураРедагувати

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

ПосиланняРедагувати