Перегляд вихідного коду сторінки Теорія Ремзі

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

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

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

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

Огляд результатів до 1990&nbsp;р. дано в роботі<ref>{{Citation|last=Graham|first=R.|title=Ramsey Theory|year=1990|last2=Rothschild|last3=Spencer|first2=B.|first3=J. H.|author-link=Рональд Грем|authorlink3=Джоел Спенсер|edition=2nd|location=New York|publisher=John Wiley and Sons|isbn=0-471-50046-1|url-access=registration|url=https://archive.org/details/ramseytheory0000grah}}.</ref>.

=== Теорема Ремзі ===
{{Докладніше|Теорема Ремзі}}
Сам Ремзі довів таку теорему:
{| id="18" style="background-color: #ffffff; margin-left: 4em; margin-right: 4em; border: 1px solid; padding: 2px;"
| class="MJX-TeXAtom-ORD" |
Нехай дано числа <math>a_1,\;a_2,\;\ldots,\;a_n</math>. Тоді існує таке число <math>R</math>, що, як би ми не пофарбували ребра [[Повний граф|повного графу]] на <math>R</math> вершинах у <math>n</math> кольорів, знайдеться або повний підграф 1-го кольору на <math>a_1</math> вершинах, або повний підграф 2-го кольору на <math>a_2</math> вершинах, … або повний підграф <math>n</math>-го кольору на <math>a_n</math> вершинах.<ref>{{citation|last=Ramsey|first=F. P.|title=On a problem of formal logic|year=1930|author-link=Френк Ремзі|journal=Proc. London Math. Soc. Series 2|volume=30|pages=264–286|doi=10.1112/plms/s2-30.1.264}}</ref>
|}
Її було узагальнено на випадок [[гіперграф]]у.

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

=== [[Теорема ван дер Вардена]] ===
Схожа за формулюванням, але відрізняється доведенням [[теорема ван дер Вардена]]:
{| id="33" style="background-color: #ffffff; margin-left: 4em; margin-right: 4em; border: 1px solid; padding: 2px;"
| displaystyle="true" scriptlevel="0" |
Для кожного набору чисел <math>a_1,\;a_2,\;\ldots,\;a_n</math> існує таке число <math>W</math>, що, як би ми не пофарбували перші <math>W</math> натуральних чисел <math>n</math> кольорів, знайдеться або [[арифметична прогресія]] 1-го кольору довжини <math>a_1</math>, або арифметична прогресія 2-го кольору довжини <math>a_2</math>, …, або арифметична прогресія <math>n</math>-го кольору довжини <math>a_n</math>.<ref>{{cite journal|authorlink=Бартель ван дер Варден|first=B. L.|last=van der Waerden|title={{lang|de|Beweis einer Baudetschen Vermutung}}|journal=Nieuw. Arch. Wisk.|volume=15|year=1927|issue=|pages=212–216}}</ref>
|}
Найменше таке число називається [[Число ван дер Вардена|числом ван дер Вардена]].

Замість множини натуральних чисел можна розглянути ґратку <math>\mathbb Z^n</math>, а арифметичних прогресій&nbsp;— фігури в ній, гомотетичні даній, і твердження теореми залишиться правильним (узагальнена теорема ван дер Вардена).

=== Теорема Хейлса&nbsp;— Джеветта ===
{| id="52" style="background-color: #ffffff; margin-left: 4em; margin-right: 4em; border: 1px solid; padding: 2px;"
|
Для будь-яких чисел <math>n</math> і <math>c</math> можна знайти число <math>H</math> таке, що якщо комірки <math>H</math>-вимірного куба зі стороною довжини <math>n</math> розфарбовано в <math>c</math> кольорів, то існує хоча б одна лінія (лінією вважаються рядки, стовпці, деякі діагоналі) з <math>n</math> одноколірних комірок.<ref>''Hales A., Jewett R.'' Regularity and positional games // Trans. Amer. Math. Soc. 106 (1963), p. 222—229.</ref>
|}
З цієї теореми випливає, що під час гри в багатовимірні хрестики-нулики при будь-якій довжині рядка та будь-якому числі гравців можна знайти таке число вимірів, що нічия буде неможлива.

=== [[Задача зі щасливим кінцем|Гіпотеза Ердеша&nbsp;— Секереша про опуклі багатокутники]] ===
{| id="52" style="background-color: #ffffff; margin-left: 4em; margin-right: 4em; border: 1px solid; padding: 2px;"
|
Для будь-якого натурального <math>N</math>, кожна достатньо велика множина точок у [[Загальне положення|загальному положенні]] на площині має підмножину з <math>N</math> точок, які є вершинами опуклого багатокутника.<ref>{{citation|title=A combinatorial problem in geometry|url=http://www.numdam.org/item?id=CM_1935__2__463_0|year=1935|last1=Erdős|last2=Szekeres|first1=P.|first2=G.|author1-link=Пал Ердеш|author2-link=Дьйордь Секереш|journal=Compositio Math|volume=2|pages=463–470|accessdate=18 лютого 2019|archive-date=19 лютого 2019|archive-url=https://web.archive.org/web/20190219183414/http://www.numdam.org/item/?id=CM_1935__2__463_0}}</ref>
|}
Згідно з гіпотезою [[Пал Ердеш|Ердеша]] та Секереша про опуклі багатокутники число точок в загальному положенні, у яких обов'язково існує опуклий <math>N</math>-кутник задається формулою:

: <math>f(N)=1+2^{N-2}</math> для всіх <math>N</math>

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

=== Теорема Крута про одноколірний [[єгипетський дріб]] ===
{| id="65" style="background-color: #ffffff; margin-left: 4em; margin-right: 4em; border: 1px solid; padding: 2px;"
|
Для будь-якої розмальовки цілих чисел більших від <math>1</math> в <math>r>0</math> кольорів існує скінченна одноколірна підмножина <math>S</math> цілих така, що

:: <math>\sum_{n\in S}1/n=1.</math>

При цьому максимальний елемент, а отже й розмір множини <math>S</math> обмежений показниковою функцією від <math>r</math> зі сталою основою.
|}
Цю {{Нп|Гіпотеза Ердеша — Грема|гіпотезу Ердеша — Грема|ru|Гипотеза Эрдёша — Грэма}} довів [[2003]] року {{Iw|Ернест Крут||en|Ernest S. Croot III}}.

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

== Див. також ==
* [[Гіпотеза Ердеша — Бура]]

== Примітки ==
{{примітки}}

== Література ==

* {{книга-ру |автор=[[Мартін Гарднер|Мартин Гарднер]] |часть=Глава 17. Теория Рамсея |заглавие=От мозаик Пенроуза к надёжным шифрам |оригинал=Penrose Tiles to Trapdoor Ciphers |ответственный=пер. с англ. Ю. А. Данилова |место={{М.}} |издательство=[[Мир (видавництво)|Мир]] |год=1993 |страницы=288—308 |страниц=416 |isbn=5-03-001991-X |тираж=10000 |ref=Гарднер}}

== Посилання ==
* [http://ega-math.narod.ru/Nquant/Ramsey.htm Теорія Ремзі] {{ref-ru}} {{Webarchive|url=https://web.archive.org/web/20190219015612/http://ega-math.narod.ru/Nquant/Ramsey.htm |date=19 лютого 2019 }}

[[Категорія:Теорія Ремзі| ]]