stringtranslate.com

Теория Рэмси

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

Примеры

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

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

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

Это также частный случай теоремы Рэмси, которая гласит, что для любого данного целого числа c , любых заданных целых чисел n 1 , ..., nc , существует число R ( n 1 ,..., nc ) , такой, что если ребра полного графа порядка R ( n 1 ,..., nc ) раскрашены в 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-е изд.), Нью-Йорк: Джон Уайли и сыновья, 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.

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