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

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

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

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

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

В турецкой пещере нашли практически целую корзину позднего бронзового века В турецкой пещере нашли практически целую корзину позднего бронзового века

Археологи обнаружили в турецкой пещере Инёню практически целую древнюю корзину

N+1
Посевная в штатном режиме Посевная в штатном режиме

Сельхозпроизводители продолжают сеять, однако работать им все сложнее

Агроинвестор
Ученые разгадали научную загадку, которая будоражила человеческие умы практически 140 лет! Ученые разгадали научную загадку, которая будоражила человеческие умы практически 140 лет!

Математики доказали, что четырехчастное разбиение Генри Дьюдени оптимально

Inc.
Я, он и его бывшая: реальные истории о манипуляциях и эмоциональной зависимости Я, он и его бывшая: реальные истории о манипуляциях и эмоциональной зависимости

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

Psychologies
Это не лень, а депрессия: 5 сигналов, что тебе нужна помощь Это не лень, а депрессия: 5 сигналов, что тебе нужна помощь

Как отличить депрессию от усталости или лени

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

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

Robb Report
12 продуктов, которые можно (и даже нужно) есть на ночь: рекомендации нутрициолога 12 продуктов, которые можно (и даже нужно) есть на ночь: рекомендации нутрициолога

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

Psychologies
Дети солнца: что делать, если ребенок родился с синдромом Дауна Дети солнца: что делать, если ребенок родился с синдромом Дауна

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

Psychologies
Топ-7 лучших автомобилей для дрифта Топ-7 лучших автомобилей для дрифта

Предлагаем наш вариант подборки топовых дрифткаров

РБК
Цена вопроса: что происходит с премиальными модными брендами в России Цена вопроса: что происходит с премиальными модными брендами в России

Что такое товары категории премиум и насколько они востребованы на рынке сейчас

Forbes
Мадам Тофана: как Мадам Тофана: как

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

VOICE
Настройка звука Настройка звука

Звуковые медитации считаются лучшим способом восстановить силы

Grazia
Что нужно знать о гримере Нике Дадмене, создавшем мастера Йоду, Мумию и гиппогрифов из «Гарри Поттера» Что нужно знать о гримере Нике Дадмене, создавшем мастера Йоду, Мумию и гиппогрифов из «Гарри Поттера»

История одного из лучших гримеров кинематографа Ника Дадмена

Правила жизни
8 лайфхаков, которые улучшат память 8 лайфхаков, которые улучшат память

Что делать, если мы начинаем забывать и то, что нужно?

Psychologies
10 лучших корейских дорам 10 лучших корейских дорам

Корейские сериалы разных жанров, от мелодрам до политического триллера

Maxim
Портрет в портрете Портрет в портрете

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

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

Без аппендикса можно жить, но есть другие органы, без которых можно обойтись

ТехИнсайдер
Аккуратно, но стильно Аккуратно, но стильно

Мужчины с чувством юмора рассуждают о чувстве стиля их собратьев по полу

Men Today
Зачем уголь Черной Бороде? Раскрыт секрет затонувшего корабля самого известного английского пирата Зачем уголь Черной Бороде? Раскрыт секрет затонувшего корабля самого известного английского пирата

На судне Эдварда Тича нашли уголь, хотя тогда его не использовали как топливо

Вокруг света
26 фактов, которые мужчины о себе не знают 26 фактов, которые мужчины о себе не знают

После этих откровений ты увидишь в зеркале совершенно другого человека

Maxim
Темная сторона Древней Греции: о чем не рассказывают детям на уроках истории Темная сторона Древней Греции: о чем не рассказывают детям на уроках истории

Мало кто из нас обрадовался бы, оказавшись в Древней Греции

Maxim
Гравитационное линзирование указало на волновую природу темной материи Гравитационное линзирование указало на волновую природу темной материи

Согласно новому исследованию, темная материя состоит из сверхлегких аксионов

N+1
Пересадка кишечной микробиоты оказалась эффективнее антибиотиков при лечении колита Пересадка кишечной микробиоты оказалась эффективнее антибиотиков при лечении колита

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

N+1
Доктор из США отдала свою почку женщине, которую она никогда не видела. Трогательная история Доктор из США отдала свою почку женщине, которую она никогда не видела. Трогательная история

История врача, которая решила спасти жизнь человека, рискнув своей жизнью

ТехИнсайдер
Как отправить папку по электронной почте: несколько удобных способов Как отправить папку по электронной почте: несколько удобных способов

Как отправить по почте целую папку с файлами? Для этого есть несколько способов

CHIP
Ида Галич: «Мы все марафонцы, а ведем себя как спринтеры» Ида Галич: «Мы все марафонцы, а ведем себя как спринтеры»

Ида Галич — почему добрые и простые истории так нас цепляют?

Psychologies
Как спастись от жары ночью, если дома нет кондиционера и вентилятора: лайфхаки, которые работают Как спастись от жары ночью, если дома нет кондиционера и вентилятора: лайфхаки, которые работают

Лайфхаки, которые помогут подготовиться к летнему сезону и жаре заранее

ТехИнсайдер
Самый простой способ обмениваться файлами между смартфоном Android и ПК Самый простой способ обмениваться файлами между смартфоном Android и ПК

Как отправлять и получать файлы между ПК и смартфоном Android напрямую

CHIP
Солнце в банке Солнце в банке

Как выбрать ту, которую по праву можно назвать «царицей полей»?

Лиза
1000 евро за царапину: как туристов обманывают с арендой машин за рубежом и почему клиент всегда неправ 1000 евро за царапину: как туристов обманывают с арендой машин за рубежом и почему клиент всегда неправ

Поговорили с экспертом о нечестных способах заработка в каршеринге

Вокруг света
Открыть в приложении