Теорія Ремзі — розділ математики, який вивчає умови, за яких у довільно сформованих математичних об'єктах зобов'язаний з'явитися певний порядок. Названа на честь Френка Ремзі.
Завдання теорії Ремзі зазвичай звучать у формі питання «скільки елементів має бути в деякому об'єкті, щоб гарантовано виконувалося задана умова чи існувала задана структура?». Найпростіший приклад:
- Довести, що в будь-якій групі з 6 осіб, знайдуться троє людей, знайомих одне з одним, або троє людей, попарно незнайомих одне з одним.
Класичні результати
Припустимо, наприклад, що ми знаємо, що кроликів розсаджено в кліток. Наскільки великим має бути щоб гарантовано в одній з кліток було принаймні 2 кроликів? Згідно з принципом Діріхле, якщо , то знайдеться клітка, в якій буде мінімум 2 кроликів. Теорія Ремзі узагальнює цей принцип.
Огляд результатів до 1990 р. дано в роботі.
Теорема Ремзі
Сам Ремзі довів таку теорему:
Нехай дано числа . Тоді існує таке число , що, як би ми не пофарбували ребра повного графу на вершинах у кольорів, знайдеться або повний підграф 1-го кольору на вершинах, або повний підграф 2-го кольору на вершинах, … або повний підграф -го кольору на вершинах. |
Її було узагальнено на випадок гіперграфу.
Мінімальне число , за якого для заданого набору аргументів існує зазначене в теоремі розфарбування, називається числом Ремзі. Питання про значення чисел Ремзі за невеликим винятком залишається відкритим.
Схожа за формулюванням, але відрізняється доведенням теорема ван дер Вардена:
Для кожного набору чисел існує таке число , що, як би ми не пофарбували перші натуральних чисел кольорів, знайдеться або арифметична прогресія 1-го кольору довжини , або арифметична прогресія 2-го кольору довжини , …, або арифметична прогресія -го кольору довжини . |
Найменше таке число називається числом ван дер Вардена.
Замість множини натуральних чисел можна розглянути ґратку , а арифметичних прогресій — фігури в ній, гомотетичні даній, і твердження теореми залишиться правильним (узагальнена теорема ван дер Вардена).
Теорема Хейлса — Джеветта
Для будь-яких чисел і можна знайти число таке, що якщо комірки -вимірного куба зі стороною довжини розфарбовано в кольорів, то існує хоча б одна лінія (лінією вважаються рядки, стовпці, деякі діагоналі) з одноколірних комірок. |
З цієї теореми випливає, що під час гри в багатовимірні хрестики-нулики при будь-якій довжині рядка та будь-якому числі гравців можна знайти таке число вимірів, що нічия буде неможлива.
(Гіпотеза Ердеша — Секереша про опуклі багатокутники)
Для будь-якого натурального , кожна достатньо велика множина точок у (загальному положенні) на площині має підмножину з точок, які є вершинами опуклого багатокутника. |
Згідно з гіпотезою Ердеша та Секереша про опуклі багатокутники число точок в загальному положенні, у яких обов'язково існує опуклий -кутник задається формулою:
- для всіх
Вони ж довели, що у множині з меншим числом точок опуклий -кутник може не існувати.
Теорема Крута про одноколірний єгипетський дріб
Для будь-якої розмальовки цілих чисел більших від в кольорів існує скінченна одноколірна підмножина цілих така, що При цьому максимальний елемент, а отже й розмір множини обмежений показниковою функцією від зі сталою основою. |
Цю [ru] довів 2003 року [en].
Особливості теорії
Для результатів у рамках теорії Ремзі характерні дві властивості. По-перше, вони неконструктивні. Доводиться, що деяка структура існує, але не пропонується жодного способу її побудови, окрім прямого перебору. По-друге, щоби шукані структури існували, потрібно, щоб об'єкти, які їх містять, складалися з дуже великого числа елементів. Залежність числа елементів об'єкта від розміру структури зазвичай, принаймні, експоненціальна.
Див. також
Примітки
- Graham, R.; Rothschild, B.; (1990), Ramsey Theory (вид. 2nd), New York: John Wiley and Sons, ISBN .
- 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
- van der Waerden, B. L. (1927). Beweis einer Baudetschen Vermutung. Nieuw. Arch. Wisk. 15: 212—216.
- Hales A., Jewett R. Regularity and positional games // Trans. Amer. Math. Soc. 106 (1963), p. 222—229.
- 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.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет