О планарности оснащенных 4-валентных графов|Василий Мантуров|Семинар КТ №16

Общеизвестна теорема Понтрягина-Куратовскго: граф можно нарисовать на плоскости, если он "не содержит графов" K_{5} и K_{3,3}. Мы рассматриваем оснащенные 4-графы, т.е. графы, в каждой вершине которых сходится 4 ребра, при этом строго фиксируется, какие ребра следует считать противоположными. При рисовании таких графов на плоскости формальная "противоположность" ребер в вершинах должна согласовываться со структурой, диктуемой плоскостью.
В ноябре 2004 академик РАН В.А.Васильев выдвинул гипотезу, которую автор доказал в тот же день: оснащенный 4-граф нельзя нарисовать на плоскости, если он содержит два цикла без общих ребер, имеющих единственное трансверсальное перекрестие. То есть два цикла могут иметь общие вершины, в которых каждый из циклов формально переходит с ребра на "не противоположное", но не наоборот.
Фактически, в мире "оснащенных 4-графов" "запрещенным" является только граф, у которого единственная вершина и два цикла, проходящие трансверсально через эту вершину. Тем самым, набор "запрещенных" графов меньше (один, а не два), да и сами графы проще, чем в общем случае. Доказательство теоремы Понтрягина-Куратовского можно свести к гипотезе Васильева.
Будет рассказано о ряде задач, связанных с оснащенными четырехвалентными графами, в частности сформулирована глобальная проблема: какие вопросы из теории графов можно решать с помощью оснащенных 4-валентных графов?
Предварительных знаний не требуется (но на неделе мы выложим несколько материалов лектора, с которыми можно будет ознакомиться).
Василий Мантуров - профессор МФТИ, специалист по геометрии и топологии, автор книг по теории узлов.
Канал t.me/turings_crossword
Страница семинара turing.tilda.ws
00:00:00 четырёхвалентные графы
00:12:20 гипотеза Васильева
00:23:50 поворачивающие обходы
00:28:50 структура источник-сток
00:40:00 перерыв
00:44:20 хордовые диаграммы
00:48:30 доказательство гипотезы
01:06:30 ответы на вопросы