Після майже 100 років спроб: математики зі США нарешті розв'язали знамениту задачу

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

Сама суть задачі Рамсея у тім, щоб знайти комбінаторний порядок, де серед великого графіка точок і лінії гарантовано можна знайти певну структуру.

Це цікаво Фахівці визначили Слово року-2023 за версією словника Collins

Вона – набір точок, або з лініями поміж них, або без цих ліній. Відповідні набори називають "кліками", а також позначають як r (s, t), де s – кількість точок з лініями, і t – кількість точок без ліній.

Звернімо увагу, що найвідоміша проблема цієї задачі – r (3,3). Вона іноді називається "теоремою про друзів і незнайомців". Пояснюється вона прикладом: у групі з шести осіб завжди можна знайти щонайменше трьох, які один одного знають, або трьох, які один одного не знають. Розв'язок r (3,3) – 6.

Пізніше з'явилася задача знаходження r (4,4). Її розв'язали і вона становить 18. Втім, найскладніша задача – r (5,5) – залишалася досі нерозв'язаною. А все тому, що пошук розв'язку ускладнює експоненціальне зростання можливих варіантів.

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

Звернімо увагу, що це наближена відповідь. Але вона близька до точного розв'язання. Науковці зазначають, що розв'язання цієї проблеми було результатом багаторічних зусиль. Це демонструє важливість наполегливості та пошуку нових підходів, щоб розв'язувати складні математичні завдання.

Ніколи не слід здаватися, незалежно від того, скільки часу це займе,
– стверджує Жак Верстрете.

Читайте також Як досягти більшого, витрачаючи меншу кількість часу: хитрощі закону Паркінсона

Він демонструє на власному прикладі, як математики продовжують досліджувати та розширювати свої знання у галузі комбінаторики та теорії графів.

• Теги:
• Популярне
• Цікавинки
• Наука
• Світ