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

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
Рестайлинг Jeep Wrangler. Чуть больше версий и возможностей Рестайлинг Jeep Wrangler. Чуть больше версий и возможностей

Что нового в рейстайлинге Jeep Wrangler

4x4 Club
Палеонтологи впервые идентифицировали череп древнего человека-денисовца Палеонтологи впервые идентифицировали череп древнего человека-денисовца

Как ученые выделили генетический материал из черепа «человека-дракона»

ТехИнсайдер
Как правильно почистить диван: секрет гениального лайфхака из TikTok с крышкой от кастрюли Как правильно почистить диван: секрет гениального лайфхака из TikTok с крышкой от кастрюли

Диван - одно из самых грязных мест в вашем доме!

ТехИнсайдер
Человечество Человечество

Обнадеживающая история

kiozk originals

Как изменились актрисы сериала "Бальзаковский возраст, или Все мужики сво…"?

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

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

Forbes
«Вы не одиноки»: 20 напоминаний тем, кто решил сдаться, — вдохновитесь идти вперед «Вы не одиноки»: 20 напоминаний тем, кто решил сдаться, — вдохновитесь идти вперед

Если вы приготовились окончательно опустить руки, советуем прочитать этот список

Psychologies
Рынок комбикормов вырос вопреки проблемам Рынок комбикормов вырос вопреки проблемам

Топ-25 крупнейших компаний выпустили более 21 млн т продукции

Агроинвестор
В человеческом мозге разглядели две системы контроля движений В человеческом мозге разглядели две системы контроля движений

Области моторной коры по-разному активируются при разных движениях тела

N+1
Шутил, готовил и копировал американцев: как менялся Иван Ургант за время работы на ТВ Шутил, готовил и копировал американцев: как менялся Иван Ургант за время работы на ТВ

Как складывалась телекарьера Ивана Урганта: собрали самые знаковые проекты

VOICE
Тихая роскошь: как дорогой минимализм стал большим модным трендом Тихая роскошь: как дорогой минимализм стал большим модным трендом

Quiet luxury — что это за тренд и почему он востребован именно сейчас?

Правила жизни
«Начальник меня не хвалит»: многие специалисты готовы мириться с низкой зарплатой, если компания будет их ценить «Начальник меня не хвалит»: многие специалисты готовы мириться с низкой зарплатой, если компания будет их ценить

Почему руководство редко отмечает успехи сотрудников

VC.RU
Хью Хефнер обожал, а муж убил: трагическая судьба звезды Playboy Дороти Страттен Хью Хефнер обожал, а муж убил: трагическая судьба звезды Playboy Дороти Страттен

Кажется, что модель Playboy Дороти Страттен вытянула счастливый билет в жизни...

VOICE
Норвежцы превратили яичную скорлупу в прототип костного трансплантата Норвежцы превратили яичную скорлупу в прототип костного трансплантата

Ученые разработали прототип костного трансплантата из аморфного фосфата кальция

N+1
Как продать квартиру в ипотеке. 4 способа не нарушить закон Как продать квартиру в ипотеке. 4 способа не нарушить закон

Ты можешь избавиться от долговых оков – продать квартиру, купленную в ипотеку

Лиза
Хит на все времена: 11 лучших ролей Хита Леджера Хит на все времена: 11 лучших ролей Хита Леджера

От хулигана Патрика до доктора Парнаса: лучшие роли Хита Леджера

Правила жизни
Мое личное тело Мое личное тело

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

Лиза
«Одни танцуют и веселятся, другие испытывают экзистенциальный кризис»: откровения вебкам-моделей комментирует психолог «Одни танцуют и веселятся, другие испытывают экзистенциальный кризис»: откровения вебкам-моделей комментирует психолог

Вебкам — с чем сталкиваются пользователи таких ресурсов с обоих сторон?

Psychologies
Роборука с камерами в пальцах научилась распознавать предметы наощупь Роборука с камерами в пальцах научилась распознавать предметы наощупь

Манипулятор научили определять предметы на ощупь

N+1
Норвежский ключ к счастливой жизни: почему человеку важно соединяться с природой Норвежский ключ к счастливой жизни: почему человеку важно соединяться с природой

Отрывок из книги «Friluftsliv: Норвежский ключ к счастливой жизни»

Forbes
«Меня как будто изнасиловали»: что такое акушерское насилие и почему оно происходит. Часть 1. Беременность «Меня как будто изнасиловали»: что такое акушерское насилие и почему оно происходит. Часть 1. Беременность

Главная проблема родильной культуры лежит на поверхности

Psychologies
5 самых захватывающих фэнтези-детективов 5 самых захватывающих фэнтези-детективов

Существуют ли увлекательные истории на стыке фэнтези и детективов?

Maxim
Как сохранить колени здоровыми: 5 советов, которые действительно помогут Как сохранить колени здоровыми: 5 советов, которые действительно помогут

Ваши колени постоянно ноют?

ТехИнсайдер
Красота спасет... жизнь: истории женщин, выживших в лагерях Красота спасет... жизнь: истории женщин, выживших в лагерях

Эти женщины смогли победить саму смерть, а главное - не предать себя

Караван историй
Какие мужчины не дарят подарки: 6 психотипов Какие мужчины не дарят подарки: 6 психотипов

То, как мужчина относится к деньгам и подаркам, зависит от его психотипа

Psychologies
Странные и отвратительные блюда, которые ели в Средневековье. Читать на голодный желудок! Странные и отвратительные блюда, которые ели в Средневековье. Читать на голодный желудок!

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

ТехИнсайдер
Евгений Хапов. Мой первый электрический... Евгений Хапов. Мой первый электрический...

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

4x4 Club
Валерия: «Старость – это когда тянет к земле. А я стремлюсь вверх!» Валерия: «Старость – это когда тянет к земле. А я стремлюсь вверх!»

Невероятно, но факт: 17 апреля Валерия отметит 55-летие

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

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

ТехИнсайдер
Открыть в приложении