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

Последовательность "синий-красный-красный-синий-красный-красный-синий-красный-красный" приведет в желтую вершину из любой другой вершины. Изображение Wikimedia Commons, созданное пользователем Quuxplusone.

63-летний израильский математик Авраам Трахтман (Avraham Trahtman), эмигрировавший в начале девяностых из России, доказал теорему, которая оставалась без доказательства 38 лет, сообщает газета The Jerusalem Post.

Доказательство будет опубликовано в Israel Journal of Mathematics. В настоящее время Трахтман работает в университете Бар-Илана, занимается алгеброй, конечными автоматами, формальными языками. Несколько лет после иммиграции Трахтман, однако, не мог устроиться по специальности, подрабатывал сторожем.

Теорема о раскраске дорог (Road colouring theorem/problem) была сформулирована израильскими математиками в 1970 году.

Упрощенное наглядное представление теоремы может выглядеть следующим образом: путешественник оказывается в лабиринте, ему нужно добраться до определенного места. От каждого перекрестка можно пойти по k дорогам, причем каждая дорога окрашена в один из k возможных цветов. Голос с неба может подсказать путешественнику последовательность цветов, которая укажет ему, по каким дорогам идти, чтобы достичь цели. Но голос с неба не знает, на каком перекрестке стоит путешественник, откуда он пойдет. Для некоторых типов лабиринтов возможна такая последовательность цветов, которая приведет путешественника к цели независимо от того, на каком перекрестке он стоит. Задача состоит в том, чтобы определить, для каких типов лабиринтов это возможно.

На иллюстрации приведен пример такого лабиринта: граф из восьми вершин, из каждой выходит по два ребра (в каждую также входит по два ребра, но идти можно только по исходящим, против стрелочки двигаться нельзя). Ребра окрашены в красный и синий цвет. Если путешественнику надо прийти в желтую вершину, голос с неба должен сказать ему "синий-красный-красный-синий-красный-красный-синий-красный-красный". Где бы ни стоял путешественник, пройдя по этой последовательности, он обязательно окажется в желтой вершине. Читатель может попробовать сам найти последовательность, гарантированно выводящую на зеленую вершину.

Формально теорема, доказанная Трахтманом, звучит следующим образом: каждый конечный сильно связный граф, все длины циклов которого взаимно просты и все вершины которого имеют одинаковое число исходящих ребер, имеет синхронизирующую раскраску. Теорема может применяться в теории графов, а также в теории конечных автоматов.

Обсудить
Наука и техника00:0117 ноября

Пробила дно

Планета-пришелец расколола Землю и сдвинула континенты
Сулейман КеримовЛазурно: российского миллиардера задержали в Ницце
Сулеймана Керимова подозревают в отмывании миллионов евро
Моя семья
Легендарный маньяк и его культ кровавых убийц держали в страхе всю Америку
Судьба генерала: Ратко Младич умрет в тюрьме
Он убивал мусульман тысячами и не щадил даже детей
Кровавая ривьера
Франция отстреливает врагов по всему миру, пока никто не видит
«Великое прошлое нас развращает»
Почему россияне не принимают себя
«Происходящее — форма женского освобождения»
Йоаким Триер о мистической драме про лесбийскую любовь и Бога
Признак оперы
Как Дмитрий Хворостовский стал главным оперным певцом России
Циркуль в глаз
Судьба еврейского художника: от украинских сказок до нацистской выставки
Что. Вы. Наделали
Как мы потеряли идеальный Porsche и снова его нашли
«Американец», который смог
Самые невероятные версии Chevrolet Corvette, от которых сносит крышу
Мистер Спок
Мы пощупали новейший Aston Martin Vantage и делимся первыми впечатлениями
Из бананов и палок
Что получается, когда машины пытаются делать в Уганде, Кении и других странах
Ловушка для планктона
Тест: Какой офис идеально вам подходит
Это чисто Питер
Сколько стоят квартиры в воспетом Шнуром городе на Неве
Берите две
Пять стран, где ипотеку дают под смешной процент
«Моя бывшая живет на помойке»
Москвич сделал из жены бомжа, и ему не стыдно