Бывший российский математик доказал "недоступную" теорему

63-летний израильский математик        Для некоторых типов лабиринтов
Авраам Трахтман (Avraham Trahtman),    возможна такая последовательность
эмигрировавший в начале девяностых     цветов, которая приведет
из России, доказал теорему, которая    путешественника к цели независимо от
оставалась без доказательства 38       того, на каком перекрестке он стоит.
лет, сообщает газета The Jerusalem     Задача состоит в том, чтобы
Post. Доказательство будет             определить, для каких типов
опубликовано в Israel Journal of       лабиринтов это возможно. На
Mathematics. В настоящее время         иллюстрации приведен пример такого
Трахтман работает в университете       лабиринта: граф из восьми вершин, из
Бар-Илана, занимается алгеброй,        каждой выходит по два ребра (в
конечными автоматами, формальными      каждую также входит по два ребра, но
языками. Несколько лет после           идти можно только по исходящим,
иммиграции Трахтман, однако, не мог    против стрелочки двигаться нельзя).
устроиться по специальности,           Ребра окрашены в красный и синий
подрабатывал сторожем. Теорема о       цвет. Если путешественнику надо
раскраске дорог (Road colouring        прийти в желтую вершину, голос с
theorem/problem) была сформулирована   неба должен сказать ему
израильскими математиками в 1970       "синий-красный-красный-синий-красный-красный-синий-красный-красный".
году. Упрощенное наглядное             Где бы ни стоял путешественник,
представление теоремы может            пройдя по этой последовательности,
выглядеть следующим образом:           он обязательно окажется в желтой
путешественник оказывается в           вершине. Читатель может попробовать
лабиринте, ему нужно добраться до      сам найти последовательность,
определенного места. От каждого        гарантированно выводящую на зеленую
перекрестка можно пойти по k           вершину. Формально теорема,
дорогам, причем каждая дорога          доказанная Трахтманом, звучит
окрашена в один из k возможных         следующим образом: каждый конечный
цветов. Голос с неба может             сильно связный граф, все длины
подсказать путешественнику             циклов которого взаимно просты и все
последовательность цветов, которая     вершины которого имеют одинаковое
укажет ему, по каким дорогам идти,     число исходящих ребер, имеет
чтобы достичь цели. Но голос с неба    синхронизирующую раскраску. Теорема
не знает, на каком перекрестке стоит   может применяться в теории графов, а
путешественник, откуда он пойдет.      также в теории конечных автоматов.