Главная
Пол Сеймур (род. 26 июля 1950 года, Плимут, Великобритания) — британский и американский математик, профессор Принстонского университета, специалист по теорией графов. Внёс большой вклад в изучение регулярных матроидов и полностью унимодулярных матриц, теоремы о четырёх цветах, бессвязных вложений, теоремы о минорах графа, гипотезы идеального графа, гипотезы Хадвигера и графов без клешней.
Слоуновский стипендиат (1983), лауреат премии Островского (2004), премии Фалкерсона (1979, 1994, 2006, 2009), премии Пойи (1983, 2004), почётный доктор Университета Уотерлу (2008), Датского технического университета (2013). Главный редактор (совместно Карстеном Томассеном) Journal of Graph Theory.
Биография
Учился в Плимутском колледже, затем — в Эксетерском колледже в Оксфорде, получив степень бакалавра в 1971 году и доктора философии в 1975 году.
В период с 1974 по 1976 год был научным сотрудником колледжа в Университетском колледже Суонси. Затем вернулся в Оксфорд, где проработал в 1976—1980 годах в качестве младшего научного сотрудника в Мертон-колледже, а в 1978—1979 годах работал в Университете Уотерлу. В 1980—1983 годы — адъюнкт-профессор, а затем профессор в государственном исследовательском Университете штата Огайо в Коламбусе, где начал исследования с Нилом Робертсоном, плодотворное сотрудничество, которое продолжалось в течение многих лет. С 1983 до 1996 года работал в Bellcore (Bell Communications Research, ныне Telcordia Technologies) в Морристауне. Также был адъюнкт-профессором в Университете Ратгерса в 1984—1987 годах и в Университете Уотерлу в 1988—1993 годах. В 1996 году стал профессором Принстонского университета.
Семья
В 1979 году женился на Шелли Макдональд из Оттавы, в браке воспитано двое детей — Эми и Эмили. Супруги расстались в 2007 году. Брат — Линорд Сеймур — профессор генотерапии в Оксфордском университете.
Научный вклад
Комбинаторика в Оксфорде в 1970-х годах доминировала над теорией матроидов, благодаря влиянию Доминика Уэлша и Обри Уильяма Инглтона. Большая часть ранних работ Сеймура, примерно до 1980 года, была посвящена теории матроидов и включала три важных труда о матроидах: докторская диссертация; работа о характеристике исключённых миноров матроидов, представленных над трехэлементным полем; и теорема о том, что все регулярные матроиды состоят из графовых и кографовых матроидов, собранных вместе простым способом (результат, за который вручена премия Пойи). С этого периода было несколько других значительных работ: статья с Уэлшом о критических вероятностях просачивания связи на квадратной решётке; статья, в которой раскрыта гипотеза двойного покрытия цикла; статья о краевом многоцветии кубических графов, которая предвещает теорему о совпадающей решётке Ласло Ловаса; статья, доказывающая, что все безмостные графы допускают нигде не нулевые 6-потоки — шаг к подтверждению гипотезы Татта о нигде не нулевом 5-потоке, и статья, решающая проблему двух путей, которая была двигателем большей части будущей работы Сеймура.
В 1980 году переехал в Университет штата Огайо, где начал работать с Нилом Робертсоном, совместные работы составили так называемый «проект графовых миноров» — серию из 23 статей, опубликованных в течение следующих тридцати лет, с несколькими значительными результатами: теорема о структуре миноров графа, что для любого фиксированного графа все графы, которые не содержат его как минор, могут быть построены из графов, которые по существу имеют ограниченный род, объединяя их вместе на небольших наборах вырезов в древовидной структуре; доказательство гипотезы Вагнера что в любом бесконечном множестве графов один из них является минором другого (и, следовательно, любое свойство графов, которое может характеризоваться исключёнными минорами, может характеризоваться конечным списком исключённых миноров); доказательство подобной гипотезы Нэша-Уильямса о том, что в любом бесконечном множестве графов один из них может быть погружен в другой; алгоритмы полиномиального времени, чтобы проверить, содержит ли граф фиксированный граф в качестве минора, и решить проблему к вершинно-непересекающихся путей для всех фиксированных k.
Примерно в 1990 году Робин Томас начал работать с Робертсоном и Сеймуром. В результате их сотрудничества в течение следующих десяти лет было подготовлено несколько важных совместных статей: доказательство гипотезы Сакса, характеризующей исключёнными минорами графы, допускающие бессвязные вложения в 3-пространстве; доказательство того, что каждый граф, который не является пятицветным, имеет полный граф с шестью вершинами в качестве второстепенного (предполагается, что теорема о четырёх цветах даёт этот результат, что является случаем гипотезы Хадвигера); с Дэном Сандерсом новое, упрощенное, компьютерное доказательство четырёхцветной теоремы; описание двудольных графов, допускающих пфаффиан ориентации; и приведение к почти плоскому случаю гипотезы Татта о том, что каждый кубический граф без моста, который не является трёхкратным, содержит граф Петерсена как минор. (Оставшийся «почти плоский случай» впоследствии был разрешён, тем самым получено полное доказательство гипотезы Татта; решение не использует теорему о четырёх цветах, и, более того, доказывает её в расширенной форме).
В 2000 году трио было поддержано Американским институтом математики для работы над сильной гипотезой идеального графа — открытой проблемой, поднятой Клодом Бержем в начале 1960-х годов. Студентка Сеймура Мария Чудновская присоединилась к группе в 2001 году, а в 2002 году четвёрка совместно доказала гипотезу. Сеймур продолжал работать с Чудновской и получил ещё несколько результатов о индуцированных подграфах, в частности (с тремя соавторами) алгоритм полиномиального времени для проверки того, является ли граф совершенным, и общее описание всех графов без клешней. Теорема Робертсона — Сеймура — результат, полученный в 2004 году на базе работ «проекта графовых миноров», устанавливающий вполне квазиупорядоченность множества неориентированных графов с отношением минорности.
В 2010-е годы в серии работ с Алексом Скоттом и частично с Чудновской, доказано две гипотезы Андраша Дьярфаша, что каждый граф с ограниченным числом клики и достаточно большим хроматическим числом имеет индуцированный цикл нечётной длины не менее пяти и имеет индуцированный цикл длины не менее любого указанного числа.