stringtranslate.com

теория Рамсея

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

Примеры

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

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

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

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

Результаты

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

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

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

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

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

Ссылки

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

Дальнейшее чтение