Американські математики вирішили знамениту задачу, над якою билися майже сто років

Дослідники з Каліфорнійського університету в Сан-Дієго, Жак Верстрете і Сем Маттеус, виявили рішення для задачі Рамсея, яка десятиліттями була головоломкою для математиків.

Суть задачі Рамсея полягає у знаходженні комбінаторного порядку, де серед великого графіка точок і ліній можна гарантовано знайти певну структуру. Ця структура являє собою набір точок, або з лініями між ними, або без таких ліній. Ці набори називаються «кліками» і позначаються як r (s, t), де s — кількість точок з лініями, і t — кількість точок без ліній.

Найвідоміша проблема Рамсея, r (3,3), іноді називається «теоремою про друзів і незнайомців». Вона пояснюється прикладом: у групі з шести осіб завжди можна знайти щонайменше трьох, які один одного знають, або трьох, які один одного не знають. Розв’язок r (3,3) — 6.

Потім з’явилася задача знаходження r (4,4), яку було розв’язано і яка становить 18. Але складніша задача r (5,5) досі залишалася невирішеною. Чому задача, яку здається легко сформулювати, така складна? Річ у тім, що пошук розв’язку ускладнюється експоненціальним зростанням можливих варіантів.

Дослідники Верстрете і Маттеус вирішили використати псевдовипадкові графіки, які виявилися більш ефективними під час наближення до розв’язання складних задач Рамсея. Вони виявили, що вибірка з псевдовипадкових графіків часто дає кращі оцінки, ніж випадкові графіки, звужуючи діапазон можливих рішень. Результатом їхнього дослідження стало наближене розв’язання для r (4,t), яке близьке до кубічної функції t.

Важливо зазначити, що це наближена відповідь, але вона близька до точного рішення. Їхнє дослідження було відправлено на розгляд до журналу Annals of Mathematics. Вчені підкреслюють, що вирішення цієї проблеми було результатом багаторічних зусиль, і це показує важливість наполегливості та пошуку нових підходів до складних математичних завдань.

«Ніколи не слід здаватися, незалежно від того, скільки часу це займе», — стверджує Жак Верстрете, демонструючи, як знаходячи розв’язки для складних задач Рамсея, математики продовжують досліджувати й розширювати свої знання в галузі комбінаторики та теорії графів.