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

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

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

Содержание

Важнейшие результаты

Предположим, например, что мы знаем, что n кроликов рассажены в m клеток. Насколько велико должно быть n, чтобы гарантированно в одной из клеток было как минимум 2 кролика? Согласно принципу Дирихле, если n > m, то найдется клетка, в которой будут минимум 2 кролика. Теория Рамсея обобщает этот принцип.

Теорема Рамсея

Основная статья: Теорема Рамсея

Сам Рамсей доказал следующую теорему:

Пусть даны числа a_1, a_2, ... a_n. Тогда существует такое число R, что, как бы мы ни покрасили рёбра полного графа на R вершинах в n цветов, найдётся либо полный подграф 1-го цвета на a_1 вершинах, либо полный подграф 2-го цвета на a_2 вершинах, … либо полный подграф n-го цвета на a_n вершинах.[1]


Она была также обобщена им на случай гиперграфа.

Минимальное число R, при котором для заданного набора аргументов a_1, a_2, ... a_n существует указанная в теореме раскраска, называется числом Рамсея. Вопрос о значениях чисел Рамсея за небольшим исключением остается открытым.

Теорема Ван-дер-Вардена

Сходна по формулировке, но отличается доказательством теорема Ван-дер-Вардена (англ.):

Для всякого набора чисел a_1, a_2, \dots, a_n существует такое число W, что, как бы мы не покрасили первые W натуральных чисел в n цветов, найдётся либо арифметическая прогрессия 1-го цвета длины a_1, либо арифметическая прогрессия 2-го цвета длины a_2, …, либо арифметическая прогрессия n-го цвета длины a_n.[2]


Вместо множества натуральных чисел можно рассмотреть решётку \mathbb Z^n, а арифметических прогрессий — фигуры в ней, гомотетичные данной, и утверждение теоремы останется верным (обобщённая теорема Ван-дер-Вардена).

Теорема Хейлса-Джеветта

Для любых чисел n и c можно найти число H такое, что если ячейки H-мерного куба со стороной длины n раскрашены в c цветов, то существует хотя бы одна строка (столбец и т.п.) из n одноцветных ячеек.[3]

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

Особенности теории

Для результатов в рамках теории Рамсея характерны два свойства. Во-первых, они не конструктивны. Доказывается, что некоторая структура существует, но не предлагается никакого способа ее построения кроме прямого перебора. Во-вторых, чтобы искомые структуры существовали, требуется, чтобы объекты их содержащие, состояли из очень большого числа элементов. Зависимость числа элементов объекта от размера структуры как минимум экспоненциальная. Рональд Грэхем предложил приз US$1000 за доказательство того, что число Ван-дер-Вардена W(2,k)<2k2.[4] Обзор результатов до 1990 г. дан в работе[5]

Примечания

  1. ↑ Ramsey, F. P. (1930), "«On a problem of formal logic»", Proc. London Math. Soc. Series 2 Т. 30: 264–286, DOI 10.1112/plms/s2-30.1.264 
  2. ↑ van der Waerden, B. L. (1927). «Beweis einer Baudetschen Vermutung». Nieuw. Arch. Wisk. 15: 212–216.
  3. ↑ Alfred Hales, Robert Jewett, Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), 222–229.
  4. ↑ Graham, Ron (2007). «Some of My Favorite Problems in Ramsey Theory». INTEGERS (The Electronic Journal of Combinatorial Number Theory 7 (2): #A2.
  5. ↑ Graham, R.; Rothschild, B. & Spencer, J. H. (1990), «Ramsey Theory» (2nd ed.), New York: John Wiley and Sons, ISBN 0-471-50046-1 .

Ссылки


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Полезное


Смотреть что такое "Теория Рамсея" в других словарях:

  • Теория принятия решений — Виктор Васнецов. Витязь на распутье. 1878 Теория принятия решений  область исследования, вовлекающая понятия и методы математики, статистики …   Википедия

  • Теория экономического роста — Стиль этой статьи неэнциклопедичен или нарушает нормы русского языка. Статью следует исправить согласно стилистическим правилам Википедии. Теория экономического роста исследует причины мирового экономического роста и причины различий доходов… …   Википедия

  • Теорема Рамсея — Теорема Рамсея  теорема комбинаторики, открытая Франком Рамсеем, встречающаяся в литературе в нескольких формулировках: Пусть , и   натуральные числа, причем . Тогда существует число , обладающее следующим свойст …   Википедия

  • Дефляционная теория истины — или дефляционизм (от лат. deflatio  «сдувание»)  семейство теорий, объединяемых заявлениями о том, что утверждения, объявляющие истинность некоего высказывания, не придают свойство истинности такому высказыванию. Теория… …   Википедия

  • Открытые проблемы в теории чисел — Теория чисел  это раздел математики, занимающийся преимущественно изучением натуральных и целых чисел и их свойств, часто с привлечением методов математического анализа и других разделов математики. Теория чисел содержит множество проблем,… …   Википедия

  • Комбинаторика — (Комбинаторный анализ)  раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана со многими другими… …   Википедия

  • Комбинаторные задачи — Комбинаторика (Комбинаторный анализ) раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисление элементов) и отношения на них (например, частичного порядка). Комбинаторика связана со многими… …   Википедия

  • Рамсей, Фрэнк Пламптон — Фрэнк Пламптон Рамсей Frank Plumpton Ramsey Дата рождения: 22 февраля 1903(1903 02 22) Место рождения: Кембридж Дата смерти …   Википедия

  • Число Грехема — Число Грехема, названное в честь Рональда Грехема, это большое число которое является верхней границей для решения некоторой проблемы в теории Рамсея. Оно стало известно широкой публике после того, как Мартин Гарднер описал его в своей колонке… …   Википедия

  • История комбинаторики — освещает развитие комбинаторики раздела конечной математики, который исследует в основном различные способы выборки заданного числа m элементов из заданного конечного множества: размещения, сочетания, перестановки, а также перечисление и смежные… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»