Теория Рэмси

Теория Рэмси , названная в честь британского математика и философа Фрэнка П. Рэмси , является ветвью математической области комбинаторики , которая фокусируется на появлении порядка в субструктуре, данной структурой известного размера. Проблемы в теории Рэмси обычно задают вопрос формы: «Насколько велика должна быть какая -то структура, чтобы гарантировать, что конкретное свойство имеет?» ^{[ 1 ]}

Примеры

Типичный результат в теории Рэмси начинается с некоторой математической структуры, которая затем разрезают на куски. Насколько велика должна быть оригинальная структура, чтобы, по крайней мере, у одной из произведений интересное свойство? Эта идея может быть определена как регулярность разделения .

Например, рассмотрим полный график порядка n ; То есть есть n вершин, и каждая вершина подключена к любой другой вершине по краю. Полный график порядка 3 называется треугольником. Теперь раскрасьте каждый край красный или синий. Насколько большим должен быть n , чтобы убедиться, что есть синий треугольник или красный треугольник? Оказывается, ответ 6. См. Статью о теореме Рэмси для строгого доказательства .

Другой способ выразить этот результат, заключается в следующем: на любой стороне с по крайней мере шестью людьми есть три человека, которые все либо взаимные знакомые (каждый из них знает двух других), либо взаимные незнакомцы (ни один из них не знает ни одного из других ) Смотрите теорему о друзьях и незнакомцах .

Это также особый случай теоремы Рэмси, в которой говорится, что для любого данного целого числа C , любые заданные целые числа n ₁ , ..., n _c , есть число, r ( n ₁ , ..., n _c ), так, что если края полного графика порядка r ( n ₁ , ..., n _c ) окрашены различными цветами C , то для некоторых I от 1 до C , он должен содержать полный подграф порядка n _i, чей края - все цвет i . Специальный случай выше имеет C = 2 и N ₁ = N ₂ = 3.

Результаты

Две ключевые теоремы теории Рэмси:

Теорема Ван дер Ваэрдена : для любого данного C и N существует число V , так что, если V последовательные числа окрашены C различными цветами, то он должен содержать арифметическое развитие длины N, элементы которых являются одинаковыми цветами.
Хейлс -теорема Джуветта : для любого данного n и c есть число H, так что, если ячейки H -мерного n × n × n × ... × n куб окрашены цветами C , должен быть один ряд , колонна и т. Д. Длина n Все ячейки которого одинаковы. То есть: многопользовательский n- in-a-row tic-tac-oe не может закончиться в ничьей, независимо от того, насколько большим N , и независимо от того, сколько людей играют, если вы играете на доске с достаточно много размеры. Теорема Хейлса - Джеветта подразумевает теорему Ван дер Ваэрдена.

Теорема, похожая на теорему Ван -дер Ваэрдена, - это теорема Шура : для любого данного C есть число N, так что, если числа 1, 2, ..., n окрашены C различными цветами, то должна быть пара целых чисел. x , y такая, что x , y и x + y - это один и тот же цвет. Существуют много обобщений этой теоремы, в том числе теорема Радо , теорему Радо -Полкман -Сандерс , теорему Хиндмана и теорему Милликен -Тейлор . Классической ссылкой для этих и многих других результатов в теории Рэмси является Грэм, Ротшильд, Спенсер и Солимоси, обновленная и расширенная в 2015 году до своего первого нового издания за 25 лет. ^{[ 2 ]}

Results in Ramsey theory typically have two primary characteristics. Firstly, they are unconstructive: they may show that some structure exists, but they give no process for finding this structure (other than brute-force search). For instance, the pigeonhole principle is of this form. Secondly, while Ramsey theory results do say that sufficiently large objects must necessarily contain a given structure, often the proof of these results requires these objects to be enormously large – bounds that grow exponentially, or even as fast as the Ackermann function are not uncommon. In some small niche cases, upper and lower bounds are improved, but not in general. In many cases these bounds are artifacts of the proof, and it is not known whether they can be substantially improved. In other cases it is known that any bound must be extraordinarily large, sometimes even greater than any primitive recursive function; see the Paris–Harrington theorem for an example. Graham's number, one of the largest numbers ever used in serious mathematical proof, is an upper bound for a problem related to Ramsey theory. Another large example is the Boolean Pythagorean triples problem.^[3]

Theorems in Ramsey theory are generally one of the following two types. Many such theorems, which are modeled after Ramsey's theorem itself, assert that in every partition of a large structured object, one of the classes necessarily contains its own structured object, but gives no information about which class this is. In other cases, the reason behind a Ramsey-type result is that the largest partition class always contains the desired substructure. The results of this latter kind are called either density results or Turán-type result, after Turán's theorem. Notable examples include Szemerédi's theorem, which is such a strengthening of van der Waerden's theorem, and the density version of the Hales-Jewett theorem.^[4]

References

^ Graham, Ron; Butler, Steve (2015). Rudiments of Ramsey Theory (2nd ed.). American Mathematical Society. p. 1. ISBN 978-0-8218-4156-3.
^ Graham, Ronald L.; Rothschild, Bruce L.; Spencer, Joel H.; Solymosi, József (2015), Ramsey Theory (3rd ed.), New York: John Wiley and Sons, ISBN 978-0470391853.
^ Lamb, Evelyn (2016-06-02). "Two-hundred-terabyte maths proof is largest ever". Nature. 534 (7605): 17–18. doi:10.1038/nature.2016.19990. PMID 27251254.
^ Furstenberg, Hillel; Katznelson, Yitzhak (1991), "A density version of the Hales–Jewett theorem", Journal d'Analyse Mathématique, 57 (1): 64–119, doi:10.1007/BF03041066.

Теория Рэмси

Примеры

Результаты

See also

References

Further reading