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

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
Леонардо Ди Каприо. «Боль временна, а фильм — навсегда» Леонардо Ди Каприо. «Боль временна, а фильм — навсегда»

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

Караван историй
Эффект Матильды: как и почему женщины в науке остаются незамеченными Эффект Матильды: как и почему женщины в науке остаются незамеченными

Почему достижения женщин в науке оставались и остаются незамеченными?

ТехИнсайдер
Где находится исток Нила? Спустя тысячи лет никто не нашел ответа на этот вопрос Где находится исток Нила? Спустя тысячи лет никто не нашел ответа на этот вопрос

Происхождение вод Нила завораживало древних египтян и до сих пор не изучено

ТехИнсайдер
Первый в мире пациент, которого удалось спасти с помощью инсулина: история Леонарда Томпсона Первый в мире пациент, которого удалось спасти с помощью инсулина: история Леонарда Томпсона

История подростка, ставшего первым пациентом в мире, получившим укол инсулина

ТехИнсайдер
Ты как ребенок: почему взрослый ведет себя по-детски? Ты как ребенок: почему взрослый ведет себя по-детски?

Порой инфантильное поведение становится чертой характера. Почему?

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

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

Forbes
Что такое IQ тесты и насколько они достоверны Что такое IQ тесты и насколько они достоверны

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

ТехИнсайдер
Какие права на квадроцикл нужны и можно ли ездить без прав Какие права на квадроцикл нужны и можно ли ездить без прав

Нужны ли права для управления квадроциклом и как их получить?

РБК
Можно ли приручить землетрясение? Можно ли приручить землетрясение?

Что мы знаем о землетрясениях?

Наука и жизнь
Это вам не мусор! Учимся с умом использовать пластиковые хомуты в доме и на даче Это вам не мусор! Учимся с умом использовать пластиковые хомуты в доме и на даче

Хомуты могут быть полезны для хранения продуктов и экспресс-ремонта одежды

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

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

N+1
История усадьбы Ивана Барышникова на Мясницкой История усадьбы Ивана Барышникова на Мясницкой

Отрывок из главы об усадьбе Барышникова на Мясницкой

СНОБ
«За океан»: cериал о том, как Комитет спасения помогал бегущим от нацизма в Америку «За океан»: cериал о том, как Комитет спасения помогал бегущим от нацизма в Америку

Мини-сериал «За океан» — экранизация романа Джули Орринджер «Портфолио полетов»

Forbes
Портрет в портрете Портрет в портрете

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

Дилетант
Лёгкость бытия Лёгкость бытия

Интерьер в стиле лёгкой современной классики в авторской интерпретации

SALON-Interior
Самые сексуальные женщины: 4 главных качества — мнение мужчин Самые сексуальные женщины: 4 главных качества — мнение мужчин

Что делает девушку сексуальной в глазах мужчин?

Psychologies
Утопия восьмибитного глобализма Утопия восьмибитного глобализма

«Тетрис» и виртуальная реальность СССР

Weekend
«Мы сделаны из звездного вещества»: какую роль в астрономии играют женщины-ученые «Мы сделаны из звездного вещества»: какую роль в астрономии играют женщины-ученые

Глава из книги «Обращенные к звездам: прошлое, настоящее и будущее астрономии»

Forbes
Кот Шрёдингера потяжелел до 16 микрограмм Кот Шрёдингера потяжелел до 16 микрограмм

Физики смогли перевести объект массой 16 микрограмм в состояние кота Шрёдингера

N+1
Все, что важно знать о кори и прививке от нее Все, что важно знать о кори и прививке от нее

Что нужно знать о кори и как защитить себя и своих близких во время вспышек кори

РБК
Заработать на журналистике и победить кликбейт и фейки: как работает Substack Заработать на журналистике и победить кликбейт и фейки: как работает Substack

Как устроен Substack и стоит ли становиться его автором или инвестором?

Forbes
О дивный тленный мир: 10 фильмов и книг, которые затрагивают тему смерти О дивный тленный мир: 10 фильмов и книг, которые затрагивают тему смерти

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

ТехИнсайдер
Как выбрать термобелье для похода? Советы эксперта Как выбрать термобелье для похода? Советы эксперта

Регулируем температуру тела правильно

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

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

ТехИнсайдер
В начале было слово: зачем нужно идти на выставку «Логос: голос конструктивизма» в центре «Зотов» В начале было слово: зачем нужно идти на выставку «Логос: голос конструктивизма» в центре «Зотов»

Мария Аборонова изучила выставку «Логос: голос конструктивизма»

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

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

Maxim
Может ли искусственный интеллект предсказывать будущее Может ли искусственный интеллект предсказывать будущее

Ограничены ли нейросети в своих возможностях?

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

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

N+1
Родители годами гнобили свою дочь и сделали из нее «Маугли». Трагичная история Джини Уайли Родители годами гнобили свою дочь и сделали из нее «Маугли». Трагичная история Джини Уайли

Единственный ребенок семьи Уайли до конца своих дней остался недееспособным

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