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

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

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

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

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

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

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

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

Обсудить
Displaced people from the minority Yazidi sect, fleeing violence from forces loyal to the Islamic State in Sinjar town, walk towards the Syrian border, on the outskirts of Sinjar mountain, near the Syrian border town of Elierbeh of Al-Hasakah Governorate August 11, 2014. Islamic State militants have killed at least 500 members of Iraq's Yazidi ethnic minority during their offensive in the north, Iraq's human rights minister told Reuters on Sunday. The Islamic State, which has declared a caliphate in parts of Iraq and Syria, has prompted tens of thousands of Yazidis and Christians to flee for their lives during their push to within a 30-minute drive of the Kurdish regional capital Arbil. Picture taken August 11, 2014. REUTERS/Rodi Said (IRAQ - Tags: POLITICS CIVIL UNREST TPX IMAGES OF THE DAY) FOR BEST QUALITY IMAGE ALSO SEE: GM1EA8M1B4V01Дважды отверженные
Почему от женщин, вырвавшихся из плена боевиков, отворачивается общество
Participants attend a gay pride parade in central Istanbul June 30, 2013. Tens of thousands of anti-government protesters teamed up with a planned gay pride march in Istanbul. Crowds were stopped by riot police from entering Taksim, the centre of previous protests, but the atmosphere appeared peacefulОпасное интернет-проникновение
Грозит ли подъем геев-мусульман исламскому миру
Китайский интерес
Пекин желает смерти уйгурским боевикам в Сирии, но вмешиваться в войну не готов


Из ЕС в сексуальное рабство
Что вынуждает румынок отправляться на Сицилию, где их ждет неволя
Парное выступление
Министры России и Японии обсудили безопасность в формате «два плюс два»
Пиджак и боб
Самое крутое автомобильное видео марта
Самые необычные ДТП
Автомобили на крышах, в бассейнах и другие непонятные аварии, достойные премии
Уже в воскресенье
Все, что нужно знать перед новым сезоном Формулы-1
Машины, которым не повезло
Посмотрите, какими могли бы быть известные машины
Бог простит
В церкви нашли квартиру с красной мебелью и портретами в стиле поп-арт
Фрэнк ГериСпугнули рыбу
Почему антисемиты изгнали из Канады создателя «танцующего дома»
«Наш дом — колония строгого режима»
История семьи, оказавшейся на грани распада из-за дачи
Цветам не место в доме
Почему дети мешают взрослым жить счастливо в собственных квартирах