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

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

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

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

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

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

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

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

Обсудить
Наука и техника00:03Сегодня
На поверхности Венеры (в представлении художника)

Русская планета

Объяснены аномальные результаты советской миссии к Венере
Дональд ТрампНесвобода вместо свободы
Что стоит за новым охлаждением отношений США и Кубы
Останки Карлоса КастаньоРоман с кокаином
В Колумбии ультраправые наркокартели невероятно жестоко расправляются с леваками
Ни поплавать, ни поездить
Самые странные санкции и неожиданные проблемы из-за них
Богемская рапсодия
Жертвоприношения, ритуалы и пьянство в самом закрытом мужском клубе США
Цена ошибки
Неправильно понятая депеша стала причиной начала Корейской войны
Тест УАЗ Пикап, VW Amarok и Fiat Fullback
Маленький триумф больших машин, или странное путешествие к странному озеру
Ралли старинных машин
Фотографии с московской гонки классических автомобилей
Тюнинг бюджетных тачек
У вас «Логан»? Не отчаивайтесь — и его можно сделать очень крутым
5 фактов об универсале Lada Vesta
Все, что пока известно о двух новых модификациях «Весты»
Вите надо выйти
Соседи несколько лет травят москвича, который отказывается переселяться
Без свидетелей
Дома для тех, кто ненавидит соседей
Москва за нами
Какие квартиры можно купить в пределах МКАД по цене до трех миллионов рублей
Классовая борьба
На смену дешевым квартирам в Москве пришел новый вид жилья
Да катитесь вы
Семейная пара отказалась от квартиры и поселилась в автобусе