Как математики сдвинули с мертвой точки диагональное число Рамсея

N+1Наука

Бери ниже

Как математики сдвинули с мертвой точки диагональное число Рамсея

Фёдор Петров

В комбинаторике прямо сейчас происходит много весьма интересных событий, это одна из самых бурно развивающихся областей математики. Но среди них отдельно выделяется новая работа Марсело Кампоса, Саймона Гриффитса, Роберта Морриса (Рио-де-Жанейро) и Джулиана Сахасрабуде (Кембридж), посвященная оценке чисел Рамсея. В чем с этими числами проблема и как ее недавно решили, рассказывает математик Фёдор Петров, профессор СПбГУ и ведущий научный сотрудник ПОМИ РАН.

Числа Рамсея

Чтобы определить числа Рамсея, начнем с задачи, которую решают на школьных математических кружках: докажите, что из любых шести людей найдутся трое попарно знакомых или трое попарно незнакомых (будем считать, что знакомство взаимно).

Возьмем любого из шестерых — назовем его Иваном. Предположим, что он знает хотя бы троих из оставшихся. Если среди этих троих есть двое знакомых, они образуют искомую тройку (попарно знакомых) с Иваном, если нет — то тройку попарно незнакомых между собой. Если же Иван знает не более двоих из оставшихся, то у него есть трое незнакомых, и для них работает аналогичное рассуждение. Также легко видеть, что в компании из пяти человек может уже не найтись троих попарно знакомых или попарно незнакомых: поставим пятерых изначально незнакомых людей по кругу и познакомим соседей.

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

Графы для R(3,3) = 6 и R(3,3) = 5. john doe

А если мы хотим найти в какой-нибудь группе больше людей, которые или каждый с каждым знакомы, или каждый с каждым не знакомы? Верно ли, что какие бы значения n и k мы не взяли, в достаточно большой компании найдутся или n попарно знакомых, или k попарно незнакомых людей? Да, верно: это доказал английский математик Фрэнк Пламптон Рамсей в 1930 году. Наименьший размер компании, заведомо удовлетворяющей этому условию, обозначается R(n,k) и называется числом Рамсея. Выше мы установили, что R(3,3)=6.

У этого графа R(4,4) = 18 вершин.
Следовательно, здесь найдутся 4 вершины соединенные либо только красными, либо только синими ребрами. Попробуйте найти такую четверку! john doe
Таких четверок в этом графе несколько, вот два из них. john doe

Считать числа Рамсея очень трудно. Известно, что:

  • R(4,3)=9,
  • R(4,4)=18,
  • R(3,5)=14,
  • R(4,5)=25 (это сложно).

А вот R(5,5) уже неизвестно. Известно только, что 43⩽R(5,5)⩽48.

Как говорил математик Пол Эрдёш больше 30 лет назад, если на Землю нападут пришельцы и потребуют в течение года назвать

Авторизуйтесь, чтобы продолжить чтение. Это быстро и бесплатно.

Регистрируясь, я принимаю условия использования

Рекомендуемые статьи

Древнего дюгоня покусали акулы и крокодил Древнего дюгоня покусали акулы и крокодил

Палеонтологи описали остатки вымершего дюгоня из рода Culebratherium

N+1
Пальчики оближешь! 5 оригинальных и очень вкусных маринадов для шашлыка Пальчики оближешь! 5 оригинальных и очень вкусных маринадов для шашлыка

Мы собрали подборку лучших маринадов для шашлыка — выбирайте любой!

ТехИнсайдер
Химики использовали иодид самария как катализатор Химики использовали иодид самария как катализатор

Как химики научились применять иодид самария в каталитических количествах

N+1
Партизаны подлинные и мнимые Партизаны подлинные и мнимые

Каким было партизанское движение во время Второй мировой войны?

Дилетант
Как повысить уровень жизни: техника маленьких шагов Как повысить уровень жизни: техника маленьких шагов

Что такое «денежный потолок» и как его расширить, улучшив качество жизни

Psychologies
Приручение скорости Приручение скорости

Национальные и мировые рекорды в автогонках на льду Байкала

Robb Report
Топ-6 самых полезных бенчмарков для смартфона Топ-6 самых полезных бенчмарков для смартфона

Рассказываем о самых полезных бенчмарках с точки зрения простого пользователя

CHIP
«Оттягивать неизбежную катастрофу»: фрагмент из биографии Анастаса Микояна «Оттягивать неизбежную катастрофу»: фрагмент из биографии Анастаса Микояна

Отрывок из биографии советского политического деятеля Анастаса Микояна

СНОБ
Портрет в портрете Портрет в портрете

Иногда атрибуции сплетаются в исторические цепочки

Дилетант
«Наполеон: биография» «Наполеон: биография»

История жизни самого известного французского императора

N+1
Палеогенетики прочитали ДНК Балто Палеогенетики прочитали ДНК Балто

Балто оказался генетически ближе всего к беспородным аляскинским ездовым собакам

N+1
Брук Шилдс: как объективация почти разрушила жизнь самой популярной модели в США Брук Шилдс: как объективация почти разрушила жизнь самой популярной модели в США

«Прелестное дитя: Брук Шилдс» — один из лучших фильмов о шоу-бизе

Forbes
«Моя красота — тяжелый труд»: как живет модель-инвалид, которая с детства не может ходить «Моя красота — тяжелый труд»: как живет модель-инвалид, которая с детства не может ходить

Каждый день из жизни Аллы Нурмагомедовой — доказательство, на что она способна

VOICE
Культура труда Культура труда

Арт-индустрия готова многое предложить тем, кто решится связать с ней свою жизнь

VOICE
Хладнокровная любовь Хладнокровная любовь

Отправляясь в апрельский лес, я не помышлял ни о какой свадьбе

Наука и жизнь
Готовимся к лету: как почистить кондиционер своими силами Готовимся к лету: как почистить кондиционер своими силами

Пошаговая инструкция, как почистить кондиционер, — будет работать как новый!

ТехИнсайдер
Мадам Тофана: как Мадам Тофана: как

Тофана — имя целой династии отравительниц

VOICE
Почему возникает мигрень? Простое объяснение и советы Почему возникает мигрень? Простое объяснение и советы

Вопреки предрассудкам, мигрень — это не просто головная боль

ТехИнсайдер
«Посмотрите правде в глаза»: что делать, если вы сожалеете о разводе — мнение психологов «Посмотрите правде в глаза»: что делать, если вы сожалеете о разводе — мнение психологов

Почему мы неожиданно начинаем скучать по бывшим партнерам?

Psychologies
«Где деньги, Лев?». Отрывок из книги о жизни дореволюционной России «Где деньги, Лев?». Отрывок из книги о жизни дореволюционной России

Почему Лев Толстой хотел лишить детей прав на свои книги

СНОБ
Земля до начала времен: как у динозавра из Южной Америки нашлась австралийская «сестра» Земля до начала времен: как у динозавра из Южной Америки нашлась австралийская «сестра»

Ученые сравнили два черепа динозавров и сделали удивительный вывод

Вокруг света
Почему мы наказываем себя и как перестать это делать? Почему мы наказываем себя и как перестать это делать?

Всегда считаете себя виноватыми в любой ситуации?

Psychologies
«Наша задача — создавать выгодные и простые сервисы для клиентов «Наша задача — создавать выгодные и простые сервисы для клиентов

Какие технологии нужны розничным клиентам?

Деньги
Записки отельера: как отделаться от итальянца за один день Записки отельера: как отделаться от итальянца за один день

Владелец отеля «Гельвеция» — о том, как оказался свидетелем детективной истории

Правила жизни
Магия цифр: как скручивают пробег автомобиля и как узнать реальные цифры Магия цифр: как скручивают пробег автомобиля и как узнать реальные цифры

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

CHIP
Кто написал «Роман с кокаином» Кто написал «Роман с кокаином»

Чем интересна повесть «Роман с кокаином» и кто на самом деле ее написал

СНОБ
Юрий Соломин: «Я человек эмоциональный, но по натуре — не диктатор, готов согласиться с другим мнением» Юрий Соломин: «Я человек эмоциональный, но по натуре — не диктатор, готов согласиться с другим мнением»

Интервью с художественным руководителем Малого театра Юрием Соломиным

Караван историй
Деликатный вопрос Деликатный вопрос

Когда вагинальные выделения — норма, а в каких случаях указывают на проблемы

Лиза
Константин Вишневский: « Даже иллюзия самостоятельности робота вызывает страх и недоверие» Константин Вишневский: « Даже иллюзия самостоятельности робота вызывает страх и недоверие»

Насколько реальна перспектива вытеснения людей «цифровыми сотрудниками»?

РБК
Смерть мужа, помолвка с магом и неизлечимая болезнь: крутые виражи в жизни звезды бразильских сериалов Сузаны Виейры Смерть мужа, помолвка с магом и неизлечимая болезнь: крутые виражи в жизни звезды бразильских сериалов Сузаны Виейры

Сузана Виейра была одной из главных икон бразильских сериалов

VOICE
Открыть в приложении