Теория Рэмси

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

Примеры [ править ]

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

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

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

Это также частный случай теоремы Рэмси, которая гласит, что для любого данного целого числа , любых заданных целых чисел n ₁ ,..., , _nc существует число R ( n ₁ ,..., nc _c ), такой, что если ребра полного графа порядка R ( n ₁ ,..., nc ₎ раскрашены в c разных цветов, то для некоторого i между 1 и c он должен содержать полный подграф порядка i _, n края все цвета i . В приведенном выше частном случае c = 2 и n ₁ = n ₂ = 3.

Результаты [ править ]

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

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

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

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

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

См. также [ править ]

Ссылки [ править ]

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

Дальнейшее чтение [ править ]

Ландман, Б.М. и Робертсон, А. (2004), Теория Рамсея для целых чисел , Студенческая математическая библиотека, том. 24, Провиденс, Род-Айленд: AMS, ISBN 0-8218-3199-2 .
Рэмси, Ф.П. (1930), «О проблеме формальной логики», Труды Лондонского математического общества , s2-30 (1): 264–286, doi : 10.1112/plms/s2-30.1.264 (за платным доступом) .
Эрдос, Пол ; Секерес, Джордж (1935), «Комбинаторная проблема в геометрии» , Compositio Mathematica , 2 : 463–470, doi : 10.1007/978-0-8176-4842-8_3 , ISBN 978-0-8176-4841-1 , Збл 0012.27010 .
Булос, Г.; Берджесс, JP; Джеффри, Р. (2007), Вычислимость и логика (5-е изд.), Кембридж: Издательство Кембриджского университета, ISBN 978-0-521-87752-7 .
Мэтью Кац и Ян Рейманн. Введение в теорию Рэмсея: быстрые функции, бесконечность и метаматематика. Студенческая математическая библиотека. Том: 87; 2018 год; 207 стр.; ISBN 978-1-4704-4290-3

[1] Грэм, Рон; Батлер, Стив (2015). Рудименты теории Рэмси (2-е изд.). Американское математическое общество. п. 1. ISBN 978-0-8218-4156-3 .

[2] Грэм, Рональд Л .; Ротшильд, Брюс Л .; Спенсер, Джоэл Х .; Солимоси, Йожеф (2015), Теория Рэмси (3-е изд.), Нью-Йорк: Джон Уайли и сыновья, ISBN 978-0470391853 .

[3] Лэмб, Эвелин (2 июня 2016 г.). «Доказательство по математике объемом в двести терабайт — самое большое за всю историю» . Природа . 534 (7605): 17–18. дои : 10.1038/nature.2016.19990 . ПМИД 27251254 .

[4] Фюрстенберг, Гилель ; Кацнельсон, Ицхак (1991), «Плотная версия теоремы Хейлса-Джеветта», Journal d'Analyse Mathématique , 57 (1): 64–119, doi : 10.1007/BF03041066 .

[1]

[2]

[3]

[4]