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

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 лет назад, если на Землю нападут пришельцы и потребуют в течение года назвать

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

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

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

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

У страдавших ожирением в детстве высокая вероятность уйти в отпуск по здоровью

N+1
Одна вокруг света: пустынная дорога к последнему морю Одна вокруг света: пустынная дорога к последнему морю

215-я серия о кругосветном путешествии Ирины Сидоренко: пингвины Патагонии

Forbes
CAR-T-терапия поставила на ноги двух пациентов с тяжелой аутоиммунной нейропатией CAR-T-терапия поставила на ноги двух пациентов с тяжелой аутоиммунной нейропатией

Частично обездвиженные заболеванием люди начали ходить с помощью CAR-T-терапии

N+1
Натуральные обезболивающие: 10 продуктов, которые помогают справиться с любыми видами болей Натуральные обезболивающие: 10 продуктов, которые помогают справиться с любыми видами болей

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

ТехИнсайдер
Укус осы: правила первой помощи и 8 советов, как его избежать Укус осы: правила первой помощи и 8 советов, как его избежать

Большой угрозы укус осы не представляет, но есть исключения

РБК
Почему аналитике ChatGPT не следует слепо доверять Почему аналитике ChatGPT не следует слепо доверять

Способен ли ChatGPT правильно выявлять тренды и делать прогнозы?

Forbes
Мир IT. Честные и зубастые Мир IT. Честные и зубастые

Сегодня IT — это “новая нефть”

Men Today
5 типов токсичных родителей: как исправить отношения — психологический разбор 5 типов токсичных родителей: как исправить отношения — психологический разбор

Пять типов токсичных матерей и отцов и способы пересмотреть отношения с ними

Psychologies
Кто может стать донором крови и костного мозга в России и как это сделать Кто может стать донором крови и костного мозга в России и как это сделать

О простых возможностях стать донором и спасти чью-то жизнь

Forbes
Денежная энергия: как богатые наследницы умножают капиталы Денежная энергия: как богатые наследницы умножают капиталы

Рассказываем о женщинах, которые смогли приумножить наследство

Forbes
«Возвращение в Сеул»: как разрыв связи с родиной ведет к потере идентичности «Возвращение в Сеул»: как разрыв связи с родиной ведет к потере идентичности

«Возвращение в Сеул» вскрывает межпоколенческие травмы и ищет пути их излечения

Forbes
Профессия мечты: чем занимается дегустатор — и почему не каждый может им стать Профессия мечты: чем занимается дегустатор — и почему не каждый может им стать

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

Psychologies
Что есть, чтобы похудеть Что есть, чтобы похудеть

Как стоит питаться, чтобы тренировки приносили наибольший эффект фигуре

Лиза
5 книг, действие которых разворачивается в разных городах России 5 книг, действие которых разворачивается в разных городах России

Книги, действие которых разворачивается по России: от Санкт-Петербурга до Сибири

СНОБ
10 глупых ляпов в кино, которые портят впечатление от фильма 10 глупых ляпов в кино, которые портят впечатление от фильма

Над фильмами работают команды профессионалов, и тем не менее ошибки случаются

VOICE
Секрет пашота: как яйцо бенедикт стало одним из самых популярных блюд в мире Секрет пашота: как яйцо бенедикт стало одним из самых популярных блюд в мире

Разбираемся в феномене яйца бенедикт

Forbes
Родители думали, что 14-летняя Наташа стала жертвой киллера. Но она скрывалась у своего парня Родители думали, что 14-летняя Наташа стала жертвой киллера. Но она скрывалась у своего парня

Все считали, что девочка пострадала от рук киллера, но на суде открылась правда

ТехИнсайдер
Нейроны мышей почувствовали ультразвук механочувствительными ионными каналами Нейроны мышей почувствовали ультразвук механочувствительными ионными каналами

Мозг «чувствует» ультразвук низкой интенсивности

N+1
В поиске потерянных лет жизни В поиске потерянных лет жизни

Факторы риска, которые ухудшают здоровье и реально сокращают жизнь

Здоровье
Почему перед футбольным матчем вместе с футболистами на поле выходят дети? Почему перед футбольным матчем вместе с футболистами на поле выходят дети?

Как зародилась традиция выходить на футбольное поле вместе с детьми?

ТехИнсайдер
Сохрани на память Сохрани на память

Что такое гиппокамп и как он работает?

Grazia
Правила жизни Фила Найта Правила жизни Фила Найта

Фил Найт: бизнесмен, сооснователь компании Nike

Правила жизни
Капиталист в стране коммунистов. Каким получился «Тетрис» с Никитой Ефремовым? Капиталист в стране коммунистов. Каким получился «Тетрис» с Никитой Ефремовым?

«Тетрис»: учдачно ли сложился американский паззл в коммунистических декорациях

Правила жизни
«О том, что Олег хочет открыть свой театр, он говорил еще когда был школьником», — вспоминают друзья Олега Ефремова «О том, что Олег хочет открыть свой театр, он говорил еще когда был школьником», — вспоминают друзья Олега Ефремова

Воспоминания об Олеге Ефремове двух его друзей

Караван историй
Ученая бессмыслица Ученая бессмыслица

«Киприанов пир» как образец эрудитски-виртуозного абсурдизма

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

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

VOICE
Как ускорить борьбу с табакокурением Как ускорить борьбу с табакокурением

Почему нужно различать потребление никотина и затяжку сигаретой

Наука
Почему мы не отдыхаем и как делать это правильно: чек-лист от психолога Почему мы не отдыхаем и как делать это правильно: чек-лист от психолога

Почему мы так склонны отказывать себе в отдыхе?

Psychologies
Кишечную микробиоту назвали фактором развития нервной анорексии Кишечную микробиоту назвали фактором развития нервной анорексии

От чего зависит развитие нервной анорексии у человека?

N+1
«Просвещать и карать» «Просвещать и карать»

Функции цензуры в Российской империи середины XIX века

N+1
Открыть в приложении