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