У 1850, Томас Пенінгтон Кіркман, математик, коли він не виконував свій головний обов’язок священика англіканської церкви, так описав свою «проблему школярки»: «П’ятнадцять дівчат зі школи виходять по троє в ряд протягом семи днів поспіль: потрібно організувати їх щодня, щоб ніхто не йшов двічі в ряд».
Для сучасного математика цю проблему найкраще уявити як гіперграф — набір вузлів, зібраних у групи по три або більше. 15 школярок є вузлами, і кожну групу з «трьох поруч» можна уявити як трикутник із трьома лініями або ребрами, що з’єднують три вузли.
Проблема Кіркмана по суті запитує, чи існує розташування цих трикутників, яке з’єднує всіх школярок одна з одною, але з додатковим обмеженням, що жодні трикутники не мають спільного ребра. Спільне речення означало б, що дві школярки повинні ходити разом більше одного разу. Це обмеження означає, що кожна дівчина щодня протягом тижня гуляє з двома новими друзями, щоб кожна можлива пара збиралася рівно раз.
Ця та інші подібні проблеми спокушували математиків протягом майже двох століть відтоді, як Кіркман поставив своє запитання. У 1973 році легендарний математик Пауль Ердеш поставив подібне. Він запитав, чи можливо побудувати гіперграф із двома, здавалося б, несумісними властивостями. По-перше, кожна пара вузлів повинна бути з'єднана рівно одним трикутником, як у школярок. Ця властивість робить граф щільним трикутниками. Друга вимога вимагає, щоб трикутники розкладалися дуже точно. (Зокрема, це вимагає, щоб для будь-якої невеликої групи трикутників було принаймні на три вузли більше, ніж трикутників.) «У вас є така дещо суперечлива поведінка, коли у вас є щільний загальний об’єкт, який не має щільних частин», — сказав Девід Конлон, математик Каліфорнійського технологічного інституту.
Цього січня, в складний 50-сторінковий доказ, четверо математиків довели, що завжди можливо побудувати такий гіперграф, якщо у вас достатньо вузлів. «Кількість технічних деталей, через які [вони] пройшли, просто щоб отримати це, це було неймовірно», — сказав Аллан Ло, математик Бірмінгемського університету. Конлон погодився: «Це справді вражаюча робота».
Дослідницька група створила систему, яка задовольнила диявольські вимоги Ердеша, почавши з випадкового процесу вибору трикутників і надзвичайно ретельно розробляючи його відповідно до своїх потреб. «Кількість складних модифікацій, які входять у доказ, насправді вражаюча», — сказав Конлон.
Їхня стратегія полягала в ретельному будуванні гіперграфа з окремих трикутників. Наприклад, уявіть наших 15 школярок. Проведіть лінію між кожною парою.
Мета тут полягає в тому, щоб накреслити трикутники поверх цих ліній так, щоб трикутники задовольняли дві вимоги: по-перше, жодні трикутники не мають спільного ребра. (Системи, які відповідають цій вимозі, називаються потрійними системами Штейнера.) По-друге, переконайтеся, що кожна маленька підмножина трикутників використовує достатньо велику кількість вузлів.
Те, як це зробили дослідники, можливо, найкраще зрозуміти за допомогою аналогії.
Скажімо, замість того, щоб складати трикутники з країв, ви будуєте будинки з кубиків Lego. Перші кілька будівель, які ви робите, екстравагантні, зі структурними підсиленнями та вигадливим орнаментом. Коли ви закінчите з ними, відкладіть їх. Вони слугуватимуть «поглиначем» — таким собі структурованим запасом.
Тепер почніть будувати будівлі з цегли, що залишилася, без особливого планування. Коли ваші запаси конструкторів Lego зменшаться, ви можете виявити, що у вас є кілька заблуканих цеглин або будинки, які є структурно неякісними. Але оскільки поглинаючі будівлі настільки перестарані та посилені, ви можете витягти кілька цеглинок тут і там і використати їх, не викликаючи катастрофи.
У випадку потрійної системи Штайнера ви намагаєтеся створити трикутники. Ваш поглинач, у цьому випадку, - це ретельно підібрана колекція країв. Якщо ви виявите, що не можете відсортувати решту системи на трикутники, ви можете використовувати деякі з країв, які ведуть до абсорбера. Потім, закінчивши це, ви розбиваєте сам поглинач на трикутники.
Поглинання не завжди працює. Але математики впоралися з процесом, знайшовши нові способи обійти перешкоди. Наприклад, потужний варіант під назвою ітераційне поглинання ділить ребра на вкладену послідовність наборів, так що кожен з них діє як поглинач для наступного за величиною.
«Протягом останнього десятиліття чи близько того відбулися значні покращення, — сказав Конлон. «Це щось на кшталт мистецтва, але на даний момент вони дійсно підняли це до рівня високого мистецтва».
Проблема Ердеша була складною навіть з ітеративним поглинанням. «Досить швидко стало зрозуміло, чому ця проблема не була вирішена», - сказав Мехтааб Соні, один із чотирьох дослідників, які її розгадали, разом із Ашвін Сах, який разом із Соні є аспірантом Массачусетського технологічного інституту; Михайло Сімкін, постдокторант Центру математичних наук і застосувань Гарвардського університету; і Метью Кван, математик в Інституті науки і технологій Австрії. «Були досить цікаві, досить складні технічні завдання».
Наприклад, в інших застосуваннях ітераційного поглинання, як тільки ви закінчите охоплювати множину — або трикутниками, для потрійних систем Штейнера, або іншими структурами для інших проблем — ви можете вважати, що з нею розібралися, і забути про неї. Однак умови Ердеша завадили чотирьом математикам зробити це. Проблемний кластер трикутників може легко включати вузли з кількох наборів поглиначів.
«Трикутник, який ви вибрали 500 кроків тому, вам потрібно якось запам’ятати, як думати про це», — сказав Соні.
Четверо зрештою зрозуміли, що якщо вони ретельно вибиратимуть трикутники, вони зможуть уникнути необхідності відстежувати кожну дрібницю. «Що краще зробити, це подумати про будь-який невеликий набір із 100 трикутників і гарантувати, що набір трикутників буде обрано з правильною ймовірністю», — сказав Соні.
Автори нової статті оптимістично налаштовані, що їхня методика може бути розширена за межі цієї однієї проблеми. Вони мають вже застосували свою стратегію до проблеми про Латинські квадрати, які схожі на спрощення головоломки судоку.
Крім того, є кілька питань, які в кінцевому підсумку можуть поступитися методам поглинання, сказав Кван. «У комбінаториці так багато проблем, особливо в теорії дизайну, де випадкові процеси є дійсно потужним інструментом». Одна з таких проблем, гіпотеза Райзера-Бруальді-Штейна, також стосується латинських квадратів і чекає на вирішення з 1960-х років.
Хоча поглинання може потребувати подальшого розвитку, перш ніж воно зможе вирішити цю проблему, воно пройшло довгий шлях з моменту свого створення 30 років тому, сказав Майя Стайн, заступник директора Центру математичного моделювання Університету Чилі. «Це те, що дійсно чудово бачити, як ці методи розвиваються».
