В субботу 13 июля я ходила на гик-пикник – этакая тусовка с налетом научности. Интереснее всего там, конечно, детям, но и взрослым тоже любопытно. Тема пикника -- "жить вечно", и среди выступавших был Обри ди Грей. Он хотя геронтолог, в прошлом году прославился среди математиков. Еще бы! – ди Грей заметно продвинулся в решении задачи о хроматическом числе плоскости.
Кстати, он сказал, что ему нравится выступать именно в России, потому что здесь ему делают мало глупых замечаний. (Наверное потому, что он приглашенный профессор в МФТИ, а там плотность глупости существенно ниже, чем в среднем по стране.) И еще сказал, что наука вот-вот отменит старение. Мне кажется, что он недооценивает род человеческий: на каждую новую технологию люди найдут новые способы, как испортить себе здоровье и жизнь.
Раньше я ди Грея никогда не видела, а внешность у него оказалась приметная.
Если бы я не знала, кто он такой, то приняла бы его не за респектабельного геронтолога, а за непритязательного программиста. Вечером дома погуглила: надо же! По образованию он информатик, а в биологию попал случайно. В конце XX века его жена изучала дрозофилий геном, и ей в лабораторию понадобился сотрудник, который бы вел базу данных по геному. Вот Обри ди Грей и подошел. Так он и занимался биоинформатикой, самостоятельно углубляясь в биологию с геронтологией.
В 2018 году он показал, что хроматическое число плоскости не меньше 5. Все удивлялись: как это, геронтолог, а получил результат, который до него не могли получить профессиональные математики. А надо было удивляться иному: надо же, биоинформатик, а сместился к геронтологии. Это, правда, уже не так удивительно.
В статье о том, что происходило в математике в последние 10 лет, я не рассказывала о хроматическом числе, так что расскажу сейчас.
Хроматическое число плоскости
Допустим, мы хотим раскрасить все точки плоскости так, чтобы между одноцветными точками расстояние никогда не было равно 1. Сколько красок для этого достаточно? Наименьшее достаточное количество красок называют хроматическим числом плоскости.
Атаку на эту задачу ведут с двух сторон: оценивают хроматическое число сверху и снизу.
Чтобы оценить сверху, раскрашивают всю плоскость, например так:
Здесь плоскость разбита на правильные шестиугольники вроде пчелиных сот. Шестиугольники раскрашены в 7 цветов. Сторона шестиугольника не слишком большая, внутри одного шестиугольника любые две точки отстоят друг от друга не более чем на 1. И не слишком маленькая, чтобы расстояние между двумя точками из разных одноцветных шестиугольников было больше 1.
Этот пример показывает, что хроматическое число плоскости не больше 7, -- семи красок достаточно.
Когда оценивают снизу, приводят в пример конечный набор точек с единичными расстояниями между ними. Раз набор конечный, можно перебрать все раскраски и увидеть, что какого-то набора цветов мало.
Вот простейший пример – равносторонний треугольник со стороной 1. Если раскрасить три его вершины двумя красками, обязательно найдется две одноцветных. Это значит, что двух цветов мало: раз три точки нельзя раскрасить двумя красками, на всю плоскость тем более двух красок не хватит. Треугольник на этой картинке – пример эквидистантного графа (длины всех ребер равны 1).
А хватит ли трех красок?
Не хватит, и чтобы это показать, нужен граф посложнее треугольника. Один из таких графов придумали братья Лео и Вильям Мозеры. Здесь есть два ромба (красный и зеленый) из правильных треугольников с общей вершиной. Противоположные вершины подвинули так, чтобы расстояние между ними (синее) было равно 1. Чтобы раскрасить 7 этих точек, трех красок не хватит, нужно хотя бы четыре. Значит, хроматическое число плоскости не меньше 4.
Это значит, что для наименьшее число цветов для раскраски плоскости лежит в промежутке от 4 до 7.
Этот результат известен с середины XX века, и с тех пор 70 лет здесь не было никакого продвижения. И это удивительно. Формулировка-то у задачи простая, доступна даже школьнику. Вариантов правильного ответа всего четыре: или 4, или 5, или 6, или 7. Не обязательно искать общую формулу, достаточно перебрать все возможные варианты. И потому задача о хроматическом числе оказалась очень заразной. Условие легко понять, ответ явно лежит где-то близко и сам просится в руки: «ну возьми меня», и все-таки ускользает – лакомый кусочек для любителей головоломок.
Вот ди Грей и заразился.
В 2018 году он придумал граф, который нельзя раскрасить в 4 краски. Для этого ему пришлось построить граф посложнее Мозеровского веретена. Он рассмотрел все допустимые раскраски графа-шестиугольника с единичными ребрами.
В верхних есть три одноцветные вершины, составляющие треугольник со стороной √3, а в нижних нет.
Затем ди Грей построил огромный сложный граф, предположил, что его можно покрасить в 4 краски, и доказал в этом предположении две противоположные вещи:
1) что в графе обязательно найдется одноцветный треугольник со стороной √3;
2) что такого треугольника в графе быть не может.
Это противоречие и означало, что построен граф, не допускающий раскраску в 4 цвета. Ди Грей постарался уменьшить число вершин в этом графе, и их осталось примерно полторы тысячи. Другие математики проверили его доказательство и даже смогли упростить граф, число вершин в графе удалось уменьшить втрое.
Рисовать такой граф бессмысленно – все равно детали сливаются. Проверку результата проводили на компьютере. В своей статье ди Грей говорит, что вычислить хроматическое число графа, в котором более тысячи вершин – слишком сложная вычислительная задача. Он только проверил, что четырех красок мало.
После ди Грея осталось всего три кандидата в хроматическое число плоскости: 5, 6 или 7. Не похоже, что его метод удастся применить для дальнейшего уточнения или обобщить на другие размерности – слишком сложные графы получатся.