Вагнер, Клаус (математик)

Вагнер изучал топологию в Кёльнском университете под руководством Карла Дёрге, который был студентом Исая Шура. Вагнер получил докторскую степень в 1937 году, защитив диссертацию, касающуюся теоремы Жордана и теоремы о четырёх красках, и преподавал в Кёльне в течение многих лет сам[2]. В 1970 году он перешёл в Дуйсбургский университет, где преподавал вплоть до выхода на пенсию в 1978 году.

Вагнер известен своим вкладом в теорию графов и, в частности, в теорию миноров графов — графов, которые можно сформировать из более крупного графа путём сжатия и удаления ребёр.

Теорема Вагнера характеризует плоские графы как точно те графы, которые не имеют в качестве минора ни полного графа K₅ с пятью вершинами, ни полного двудольного графа K_3,3 с тремя вершинами в каждой из двух долей. То есть эти два графа являются единственными минимальными неплоскими графами. Она связана с теоремой Куратовского, которая гласит, что планарные графы — это именно те графы, которые не содержат в качестве подграфа подразделение K₅ или K_3,3, при этом теорема Вагнера слабее.

Граф Вагнера

Другой его результат, также известный как теорема Вагнера, состоит в том, что четырёхсвязный граф является плоским тогда и только тогда, когда он не имеет минора K₅. Из этого следует характеризация графов без минора K₅ как построенных из плоских графов и графа Вагнера (восьмивершинная лестница Мёбиуса) с помощью сумм по клике — операций, которые склеивают подграфы в кликах до трёх вершин и затем, возможно, удаляют рёбра из тех клик. Эта характеризация была использована Вагнером, чтобы показать, что случай k = 5 гипотезы Хадвигера о хроматическом числе графов без K_k-миноров эквивалентен теореме о четырёх красках. Аналогичные характеризации других семейств графов в терминах слагаемых их разложений по кликам стали с тех пор стандартными в теории минорных графов.

Вагнер предположил в 1930-х годах (хотя опубликовал позднее)[3], что в любом бесконечном наборе графов один граф изоморфен минору другого. Справедливость этой гипотезы влечёт, что любое семейство графов, замкнутых относительно операции взятия миноров (например, плоские графы), может автоматически характеризоваться конечным числом запрещённых миноров, аналогично теореме Вагнера, характеризующей планарные графы. Нил Робертсон и Пол Сеймур опубликовали доказательство этого утверждения в 2004 году и теперь оно известно как теорема Робертсона – Сеймура[4].

В 1990 году коллеги Вагнера опубликовали в честь него фестшрифт[5], а в июне 2000 года в Кёльнском университете в память об этом преподавателе был организован коллоквиум[6].

Wagner, K. (1937), «Über eine Eigenschaft der ebenen Komplexe» (недоступная ссылка), Mathematische Annalen, 114: 570—590, doi:10.1007/BF01594196