Теория Рамсея - Ramsey theory

О теории бесконечных множеств Рамсея см. Бесконечная комбинаторика.

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

Примеры

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

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

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

Это тоже частный случай Теорема Рамсея, который говорит, что для любого данного целого числа c, любые заданные целые числа п1,...,пc, есть номер, р(п1,...,пc) такая, что если ребра полного графа порядка р(п1,...,пc) окрашены c разные цвета, то для некоторых я от 1 до c, он должен содержать полный подграф заказа пя чьи края все цветные я. В приведенном выше частном случае c = 2 и п1 = п2 = 3.

Результаты

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

  • Теорема Ван дер Вардена: Для любого данного c и п, есть номер V, так что если V последовательные числа окрашены c разных цветов, то он должен содержать арифметическая прогрессия длины п все элементы одного цвета.
  • Теорема Хейлза – Джеветта: Для любого данного п и c, есть номер ЧАС такой, что если клетки ЧАС-размерный п×п×п×...×п куб окрашены c цвета, должна быть одна строка, столбец и т. д. длины п все ячейки одного цвета. То есть: мультиплеер п-в ряд крестики-нолики не может закончиться ничьей, каким бы большим он ни был п есть, и неважно, сколько людей играет, если вы играете на доске с достаточно большим количеством измерений. Из теоремы Хейлза – Джеветта следует Теорема Ван дер Вардена.

Теорема, аналогичная теореме Ван дер Вардена, имеет вид Теорема Шура: для любого данного c есть номер N такие, что если числа 1, 2, ..., N окрашены c разных цветов, то должна быть пара целых чисел Икс, у такой, что Икс, у, и Икс+у все одного цвета. Существует множество обобщений этой теоремы, в том числе Теорема Радо, Теорема Радо – Фолкмана – Сандерса, Теорема Хиндмана, а Теорема Милликена – Тейлора. Классическим эталоном для этих и многих других результатов в теории Рамсея является Грэм, Ротшильд, Спенсер и Солимози, обновленная и расширенная в 2015 году до своего первого нового издания за 25 лет.[2]

Результаты теории Рамсея обычно имеют две основные характеристики. Во-первых, они неконструктивный: они могут показать, что некоторая структура существует, но они не дают процесса для поиска этой структуры (кроме перебор ). Например, принцип голубятни имеет такую ​​форму. Во-вторых, хотя результаты теории Рамсея говорят, что достаточно большие объекты обязательно должны содержать заданную структуру, часто для доказательства этих результатов требуется, чтобы эти объекты были чрезвычайно большими - границы, которые растут экспоненциально, или даже так быстро, как Функция Аккермана не редкость. В некоторых небольших нишевых случаях улучшаются верхние и нижние границы, но не в целом. Во многих случаях эти оценки являются артефактами доказательства, и неизвестно, можно ли их существенно улучшить. В других случаях известно, что любая граница должна быть чрезвычайно большой, иногда даже большей, чем любая примитивно рекурсивный функция; увидеть Теорема Пэрис – Харрингтона для примера. Число Грэма, одно из самых больших чисел, когда-либо использовавшихся в серьезном математическом доказательстве, является верхней границей проблемы, связанной с теорией Рамсея. Другой крупный пример - Проблема логических троек Пифагора.[3]

Теоремы в теории Рамсея обычно относятся к одному из следующих двух типов. Многие такие теоремы, смоделированные на основе самой теоремы Рамсея, утверждают, что в каждом разделе большого структурированного объекта один из классов обязательно содержит большой структурированный подобъект, но не дают информации о том, к какому классу это относится. В других случаях причина Рамсеевского типа в результате самый большой класс раздела всегда содержит желаемую подструктуру. Результаты такого рода называются результаты плотности или Результат типа Турана, после Теорема Турана. Известные примеры включают Теорема Семереди, которое является таким усилением теоремы Ван дер Вардена и плотностной версии теоремы Хейлса-Джеветта.[4]

Смотрите также

Заметки

  1. ^ Грэм, Рон; Батлер, Стив (2015). Основы теории Рамсея (2-е изд.). Американское математическое общество. п. 1. ISBN  978-0-8218-4156-3.
  2. ^ Грэм, Рональд Л.; Ротшильд, Брюс Л.; Спенсер, Джоэл Х.; Солимоши, Йожеф (2015), Теория Рэмси (3-е изд.), Нью-Йорк: Джон Вили и сыновья, ISBN  978-0470391853.
  3. ^ Лэмб, Эвелин (2016-06-02). «Математическое доказательство в двести терабайт - самое большое доказательство». Природа. 534 (7605): 17–18. Дои:10.1038 / природа.2016.19990. PMID  27251254.
  4. ^ Фюрстенберг, Гилель; Кацнельсон, Ицхак (1991), "Плотная версия теоремы Хейлса-Джеветта", Журнал д'анализа математика, 57 (1): 64–119, Дои:10.1007 / BF03041066.

использованная литература