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

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
История самого русского напитка: как в Российской империи появилась водка История самого русского напитка: как в Российской империи появилась водка

В дореволюционной России водка была атрибутом успешной жизни

ТехИнсайдер
Перепрошивка памяти: новая модель памяти, которая работает как мозг Перепрошивка памяти: новая модель памяти, которая работает как мозг

Ученые создали модель памяти, устойчивую к шуму и забыванию

ТехИнсайдер
В ГИБДД назвали 10 главных штрафов. Как их избежать В ГИБДД назвали 10 главных штрафов. Как их избежать

За что штрафуют чаще всего и можно избежать «писем счастья»

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

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

VOICE
Отпусти и забудь Отпусти и забудь

Как «сжигать мосты» и не жалеть об этом

Лиза
Холод полезен для здорового старения: он запускает механизм очищения клеток Холод полезен для здорового старения: он запускает механизм очищения клеток

Как холод влияет на человеческий организм?

ТехИнсайдер
Корюшка Корюшка

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

Здоровье
Физики повторили знаменитый эксперимент с волнами света, на этот раз заставив их проходить сквозь щели во времени Физики повторили знаменитый эксперимент с волнами света, на этот раз заставив их проходить сквозь щели во времени

Исследователи воспроизвели эксперимент с двумя щелями с помощью лазеров

ТехИнсайдер
«Певчие избранники России»: что мы знаем о дроздах — обитателях лесов и городов «Певчие избранники России»: что мы знаем о дроздах — обитателях лесов и городов

У этих прожорливых пернатых, с которыми воюют садоводы, есть немало достоинств

Вокруг света
Расчлененка смысла Расчлененка смысла

«Алиса в Стране чудес» как утопия абсурда

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

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

ТехИнсайдер
26 фактов, которые мужчины о себе не знают 26 фактов, которые мужчины о себе не знают

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

Maxim
Юлия Такшина: «С возрастом понимаешь — никакой катастрофы от того, что рядом с тобой нет надежного плеча, не произойдет» Юлия Такшина: «С возрастом понимаешь — никакой катастрофы от того, что рядом с тобой нет надежного плеча, не произойдет»

Юлии Такшиной удается быть востребованной актрисой и воспитывать двоих сыновей

Караван историй
«Метла» метет по-старому: каким получился новый альбом группы Metallica «Метла» метет по-старому: каким получился новый альбом группы Metallica

Святослав Иванов рассказывает о феномене группы Metallica

Forbes
Голливудская «Аллея славы» Forbes: самые богатые знаменитости в истории Голливудская «Аллея славы» Forbes: самые богатые знаменитости в истории

Собственная голливудская «Аллея славы» Forbes

Forbes
Вы будете удивлены: топ-10 слов, которым нет (или Вы будете удивлены: топ-10 слов, которым нет (или

Просторечия, которые портят нашу жизнь

ТехИнсайдер
Какие повседневные действия сжигают больше всего калорий? Какие повседневные действия сжигают больше всего калорий?

Сколько калорий сжигает зарядка, вскапывание грядок и строительство снеговиков?

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

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

Psychologies
Правила жизни Сергея Рахманинова Правила жизни Сергея Рахманинова

Правила жизни композитора, дирижера и пианиста Сергея Рахманинова

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

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

Forbes
Олимпийская спортсменка сменила коньки на эротические фото: кто такая Александра Янкулеску и что она делает на OnlyFans Олимпийская спортсменка сменила коньки на эротические фото: кто такая Александра Янкулеску и что она делает на OnlyFans

Канадская рекордсменка румынского происхождения продает свои обнаженные фото

Maxim
Эффект наращивания: 5 домашних способов отрастить длинные и крепкие ногти Эффект наращивания: 5 домашних способов отрастить длинные и крепкие ногти

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

VOICE
«Полезно для психики»: 5 причин составлять списки «Полезно для психики»: 5 причин составлять списки

Ведение списков — отличная терапевтическая практика

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

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

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

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

Правила жизни
Партизаны подлинные и мнимые Партизаны подлинные и мнимые

Каким было партизанское движение во время Второй мировой войны?

Дилетант
Как секс-торговцы в США использовали семейное приложение для слежки за жертвами Как секс-торговцы в США использовали семейное приложение для слежки за жертвами

Life360 использовалось в качестве цифрового «поводка» в секс-торговле

Forbes
7 нескучных методов перебороть себя и начать заниматься спортом 7 нескучных методов перебороть себя и начать заниматься спортом

Чем менее активный образ жизни ведет человек, тем сложнее ему начать двигаться

Правила жизни
«Прыжок веры» в реальной жизни: сумасшедший трюк каскадера «Прыжок веры» в реальной жизни: сумасшедший трюк каскадера

Что такое «Прыжок веры» и можно ли его исполнить в реальной жизни?

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