"Радужные раскраски" недавно привели к новому доказательству
В феврале 2020 года было сообщено о решении проблемы под названием "Догадка Рингеля". Часть доказательств была связана с использованием радужных раскрасок, специальных цветовых кодов для визуализации информации. Красочная техника на самом деле долгое время помогала математикам решать головоломки, и она фигурирует в еще более сложной проблеме, которую математики описывают следующим образом.
Догадка Рингеля - это проблема в комбинаторах, где точки (вершины) соединяются с линиями (ребрами) для формирования графов. Она предсказывает, что существует особая связь между типом большого графа с вершинами 2n + 1 и пропорционально меньшим типом графа с вершинами n + 1.
Для примера начните с 11 вершин. Соедините каждую вершину с каждой другой вершиной, чтобы сформировать так называемый полный граф. Отдельно возьмите шесть вершин и соедините их любым удобным для Вас способом. Если Вы не создаете при этом замкнутых циклов, у вас должно получиться "дерево".
Догадка Рингеля гласит, что копии любого дерева, которое вы делаете, могут быть использованы для идеального покрытия, или плитки, края соответствующего полного графа так же, как вы могли бы использовать идентичные плитки для покрытия пола кухни.
Как и в случае с полом на кухне, нахождение правильного места для первой плитки имеет большое значение для выполнения общей работы по укладке плитки. Три математика, стоящие за этой гипотезой, закрасили края полного графа, основываясь на расстоянии между вершинами, чтобы найти это расположение.
Затем они попытались поместить дерево внутри полного графа так, чтобы оно покрывало по одному краю каждого цвета. Показывая, что такое "радужное" размещение всегда возможно, они доказали, что идеальная плитка, которую предсказывал Рингель, всегда срабатывает.
Это был не первый раз, когда пригодилась техника радуги.
В 18 веке Леонхард Эйлер заинтересовался своего рода сыном Судоку. Возьмем, к примеру, сетку 3 на 3. Эйлер заполнил ее так, чтобы каждый ряд и столбец содержал цифры с 1 по 3, без повторения номеров. Эта головоломка называется латинским квадратом. Узоры и приёмы, которые Эйлер и другие математики обнаружили при изучении латинских квадратов, имеют связи со многими различными областями математики.
Тогда Эйлер спросил себя: Можно ли выбрать три клетки - по одной из каждой колонки и по одной из каждой строки - так, чтобы каждая из них содержала разное число? Допустим, вы выбрали клетку в первой строке, первого столбца, которая содержит 1 клетку во второй строке, второго столбца, которая содержит 3 клетки, и клетку в третьей строке, третьего столбца, которая содержит 2 клетки. Теперь вы выбрали три клетки, каждая из которых в разных строках и разных столбцах, а также каждая из которых содержит отдельное число: 1, 3, 2. Такой набор клеток называется поперечным.
Эйлер хотел узнать, можно ли всю сетку 3 на 3 (или квадратные сетки любого размера) идеально разделить на поперечные множества, каждое из которых содержит одно отдельное число из каждой строки и столбца. Таким образом, в случае квадрата 3 на 3 вы бы могли найти три различных поперечных набора, которые бы в совокупности учитывали все квадраты в сетке.
В конце концов, математики обнаружили, что один из способов исследовать это - превратить квадрат в граф. Для этого поместите три вершины, представляющие три столбца, с левой стороны страницы. Затем поместите три вершины, представляющие строки, с правой стороны страницы. Нарисуйте края, соединяющие каждую вершину справа с каждой вершиной слева. Каждый край, являясь комбинацией определенной строки и столбца, представляет собой один из девяти секторов. Например, ребро между верхней вершиной справа и верхней вершиной слева соответствует ячейке в первой строке и первой колонке (верхняя левая ячейка на латинском квадрате).
Теперь достаньте цветные карандаши и нанесите цветовую кодировку на края, в соответствии с номером в сетке, которую они представляют. Допустим, мы будем использовать синий цвет для любых линий, представляющих 1, красный - 2, желтый - 3. Если в левом верхнем поле есть 1, то край между верхними вершинами будет синим.
Изучите цвета ребер. Можно ли выделить три ребра, представляющих все три цвета, чтобы их начальная и конечная вершины были разными? Такое выделение называется радужным согласованием. Если вы сможете его найти, то знайте, что соответствующий латинский квадрат действительно существует. Более того, если вы найдете три различных совпадения радуги, вы докажите, что весь латинский квадрат состоит из поперечных.
Радужные раскраски помогли исследователям изучить проблемы прошлого, и они стали ключом к новому доказательству догадки Рингеля. Они также играют роль в еще более сложной проблеме, называемой изящной маркировочной догадкой.