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

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
Для чего мурлыкают кошки и как громко они могут это делать Для чего мурлыкают кошки и как громко они могут это делать

Почему кошки мурлычат и как они это делают?

ТехИнсайдер
Древнему жителю Китаю ампутировали ногу в наказание Древнему жителю Китаю ампутировали ногу в наказание

Ампутацию считают древнейшей хирургической операцией

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

Когда-то Людмила Норсоян приехала в Москву с одним чемоданом, набитым книгами

Forbes
Почему в жару отекают ноги и как снять отек Почему в жару отекают ноги и как снять отек

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

РБК
Стильно, комфортно Стильно, комфортно

Современный интерьер с классическими декоративными приёмами

SALON-Interior
Самая токсичная парочка в футболе — союз бывшей порнозвезды и одноклубника Месси. Они раздражают всех Самая токсичная парочка в футболе — союз бывшей порнозвезды и одноклубника Месси. Они раздражают всех

Странная любовь Мауро Икарди и Ванды Нары

Maxim
Почему в России так популярны фильмы Marvel — мнение психолога Почему в России так популярны фильмы Marvel — мнение психолога

Что притягивает нас в супергеройских картинах?

Psychologies
Страшный хищник: кто такой лигр и как он выглядит Страшный хищник: кто такой лигр и как он выглядит

Чем лигры отличаются от своих родителей — львов и тигров?

ТехИнсайдер
Почему мюзикл «Призрак оперы» закрыли на Бродвее после 35 лет проката Почему мюзикл «Призрак оперы» закрыли на Бродвее после 35 лет проката

Чем мюзикл «Призрак оперы» запомнился миру и почему прекратил свое существование

СНОБ
Как на самом деле женщины и мужчины относятся к браку: ожидания, страхи и приоритеты — объяснение психологов Как на самом деле женщины и мужчины относятся к браку: ожидания, страхи и приоритеты — объяснение психологов

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

Psychologies
В ментоловом паре электронных сигарет нашли больше микрочастиц В ментоловом паре электронных сигарет нашли больше микрочастиц

Ментоловые электронные сигареты могут быть более вредными для здоровья

N+1
«Террорист победил»: как революционеры-радикалы боролись с властью в царской России «Террорист победил»: как революционеры-радикалы боролись с властью в царской России

История терроризма в царской России XIX-XX веков

Forbes
Научиться массажу и пойти на кулинарные курсы: 30 приключений для пары — выберите подходящие занятия Научиться массажу и пойти на кулинарные курсы: 30 приключений для пары — выберите подходящие занятия

Когда вы с партнером последний раз вместе смеялись или дурачились?

Psychologies
Цена монархии Цена монархии

Как дорого короли обходятся подданным

Деньги
Как очистить чайник от накипи: 5 способов и средств Как очистить чайник от накипи: 5 способов и средств

Как отмыть чайник от накипи с помощью средств, которые есть на каждой кухне

CHIP
Зоя Богуславская: «Портреты эпохи: Андрей Вознесенский, Владимир Высоцкий, Юрий Любимов...» Зоя Богуславская: «Портреты эпохи: Андрей Вознесенский, Владимир Высоцкий, Юрий Любимов...»

Фрагмент главы из книги «Портреты эпохи» Зои Богуславской

СНОБ
Шеф-повара китайских ресторанов — о национальных вкусах и жизни в России Шеф-повара китайских ресторанов — о национальных вкусах и жизни в России

Насколько велика ментальная разница между жителями Поднебесной и россиянами

РБК
10 страшных игр, в которые лучше не играть ночью 10 страшных игр, в которые лучше не играть ночью

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

Maxim
Борис Невзоров. Позднее счастье и незабытая трагедия Борис Невзоров. Позднее счастье и незабытая трагедия

У него действительно была очень сложная личная жизнь

Коллекция. Караван историй
26 советов отца, которые помогли мне найти любовь 26 советов отца, которые помогли мне найти любовь

Журналистка собрала советы отца, которые помогли ей встретить свою любовь

Psychologies
Одна вокруг света: пустынные пейзажи Патагонии и путешествие через нацпарк Пуйеуэ Одна вокруг света: пустынные пейзажи Патагонии и путешествие через нацпарк Пуйеуэ

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

Forbes
7 типов неудобных собеседников: как с ними общаться? 7 типов неудобных собеседников: как с ними общаться?

Разберем наиболее сложные типажи собеседников, а также способы общения с ними

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

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

Лиза
Средневековые гренландские скандинавы импортировали древесину с северо-востока Северной Америки Средневековые гренландские скандинавы импортировали древесину с северо-востока Северной Америки

По крайней мере часть древесины поступала в Гренландию в виде импорта

N+1
Мировой отец! Донор спермы в Нидерландах врал в опросах и стал отцом 550 детей за 16 лет Мировой отец! Донор спермы в Нидерландах врал в опросах и стал отцом 550 детей за 16 лет

Донор не должен быть отцом более 25 детей, но один мужчина обошел это условие

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

Как справляться с отношениями на расстоянии?

Psychologies
«Образцовые» и «ненадежные»: как работает китайский социальный рейтинг «Образцовые» и «ненадежные»: как работает китайский социальный рейтинг

Разбираемся, как работает социальный рейтинг в Китае

РБК
«Скандал показал истинную сущность моих соперников»: Влад Череватый о закулисье шоу «Экстрасенсы. Битва сильнейших» «Скандал показал истинную сущность моих соперников»: Влад Череватый о закулисье шоу «Экстрасенсы. Битва сильнейших»

Интервью с экстрасенсом Владом Череватым

VOICE

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

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