Дослідники з Каліфорнійського університету в Сан-Дієго, Жак Верстрете та Сем Маттеус, розгадали головоломку для математиків, з якою вони боролися протягом десятиліть – завдання Рамсея. Про це пише "ua.news".
Суть завдання Рамсея полягає у знаходженні комбінаторного порядку, в якому серед безлічі точок та ліній можна гарантовано виявити певну структуру. Ця структура є набір точок, з'єднаних лініями або не з'єднаних. Такі набори називаються "кліками" і позначаються як 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. Вчені підкреслюють, що вирішення цієї проблеми стало результатом багаторічних зусиль, що наголошує на важливості наполегливості та пошуку нових підходів до складних математичних завдань.
"Важливо не здаватися, незалежно від того, скільки часу це займе", - наголошує Жак Верстрете, показуючи, що, вирішуючи складні завдання Рамсея, математики продовжують досліджувати та розширювати свої знання у галузі комбінаторики та теорії графів.
Раніше "Стіна" повідомляла, що сниться людям перед смертю.
Також ми писали про метод, який змусить вас поринути у сон за 60 секунд.
Раніше ми називали 10 способів, які допоможуть швидко заснути у спеку.