Сеймур, Пол (математик)

Учился в Плимутском колледже, затем — в Эксетерском колледже в Оксфорде, где получил степень бакалавра в 1971 году, магистра наук (M.Sc.) в 1972 году, а также степени доктора философии (D.Phil) и магистра искусств (MA) в 1975 году. Его докторская диссертация под руководством Обри Уильяма Инглтона была посвящена теме «Матроиды, гиперграфы и теорема о максимальном потоке и минимальном разрезе» (англ. Matroids, Hypergraphs and the Max-Flow Min-Cut Theorem).

В период с 1974 по 1976 год был научным сотрудником колледжа в Университетском колледже Суонси. Затем вернулся в Оксфорд, где проработал в 1976—1980 годах в качестве младшего научного сотрудника в Мертон-колледже, а в 1978—1979 годах работал в Университете Уотерлу. В 1980—1983 годы — адъюнкт-профессор, а затем профессор в государственном исследовательском Университете штата Огайо в Коламбусе, где начал исследования с Нилом Робертсоном, плодотворное сотрудничество, которое продолжалось в течение многих лет. С 1983 до 1996 года работал в Bellcore (Bell Communications Research, ныне Telcordia Technologies) в Морристауне. Также был адъюнкт-профессором в Университете Ратгерса в 1984—1987 годах и в Университете Уотерлу в 1988—1993 годах. В 1996 году стал профессором Принстонского университета. В 2016 году был назначен профессором математики имени Альберта Болдуина Дода (англ. Albert Baldwin Dod Professor of Mathematics), а в 2019 году — приглашённым профессором в Оксфордском университете^[3].

Удостоен почётных докторских степеней Университета Уотерлу (2008), Датского технического университета (2013) и Высшей нормальной школы Лиона (2022).

Премии и награды

• Премия Фалкерсона (четырежды):
  • 1979
  • 1994 (совместно с Нилом Робертсоном и Робином Томасом)
  • 2006 (совместно с Нилом Робертсоном)
  • 2009 (совместно с Марией Чудновской, Нилом Робертсоном и Робином Томасом)
• Премия Пойи (дважды):
  • 1983
  • 2004 (совместно с Нилом Робертсоном)
• Стипендия Слоуна (1983).
• Премия Островского (2004).
• Памятная медаль Университета Коменского (2019)^[4].

Почётные звания и членство

• Член Лондонского королевского общества (2022).
• Почётные докторские степени:
  • Университет Уотерлу (2008)
  • Датский технический университет (2013)
  • Высшая нормальная школа Лиона (2022)

Прочее

• Приглашённый докладчик на Международном конгрессе математиков (1986).
• Пленарный докладчик на Международном конгрессе математиков (1994).

Несколько учеников Пола Сеймура добились значительных успехов в области теории графов и комбинаторики. Наиболее известной из них является Мария Чудновская, израильско-американский математик, профессор Принстонского университета, где она ранее защитила диссертацию под руководством Сеймура^[5]. Будучи его аспиранткой, она в соавторстве с Сеймуром, Нилом Робертсоном и Робином Томасом доказала сильную гипотезу о совершенных графах, за что в 2009 году они были удостоены премии Фалкерсона^[5]. В 2012 году Чудновская также получила стипендию фонда Мак-Артура^[6].

Среди других известных учеников:

• Сан-иль Ум (англ. Sang-il Oum) — южнокорейский математик, профессор KAIST и руководитель группы дискретной математики в Институте фундаментальных наук (IBS)^[7].
• Софи Спиркл (англ. Sophie Spirkl) — доцент в Университете Уотерлу, лауреат стипендии Слоуна^[8]. Защитила диссертацию под совместным руководством Пола Сеймура и Марии Чудновской^[9].
• Голи Дин (англ. Guoli Ding) — профессор математики в Университете штата Луизиана, носящий звание «Hubert Butts Professor»^[10].
• Мэтью Девос (англ. Matthew DeVos) — доцент на кафедре математики в Университете Саймона Фрейзера^[11].

В 1979 году женился на Шелли Макдональд из Оттавы, в браке воспитано двое детей — Эми и Эмили. Супруги расстались в 2007 году. Брат — Линорд Сеймур — профессор генотерапии в Оксфордском университете.

Комбинаторика в Оксфорде в 1970-х годах доминировала над теорией матроидов, благодаря влиянию Доминика Уэлша и Обри Уильяма Инглтона. Большая часть ранних работ Сеймура, примерно до 1980 года, была посвящена теории матроидов и включала три важных труда о матроидах: докторская диссертация; работа о характеристике исключённых миноров матроидов, представленных над трехэлементным полем; и теорема о том, что все регулярные матроиды состоят из графовых и кографовых матроидов, собранных вместе простым способом (результат, за который вручена премия Пойи). С этого периода было несколько других значительных работ: статья с Уэлшом о критических вероятностях просачивания связи на квадратной решётке; статья, в которой раскрыта гипотеза двойного покрытия цикла; статья о краевом многоцветии кубических графов, которая предвещает теорему о совпадающей решётке Ласло Ловаса; статья, доказывающая, что все безмостные графы допускают нигде не нулевые 6-потоки — шаг к подтверждению гипотезы Татта о нигде не нулевом 5-потоке, и статья, решающая проблему двух путей, которая была двигателем большей части будущей работы Сеймура.

В 1980 году переехал в Университет штата Огайо, где начал работать с Нилом Робертсоном, совместные работы составили так называемый «проект графовых миноров» — серию из 23 статей, опубликованных в течение следующих тридцати лет, с несколькими значительными результатами: теорема о структуре миноров графа, что для любого фиксированного графа все графы, которые не содержат его как минор, могут быть построены из графов, которые по существу имеют ограниченный род, объединяя их вместе на небольших наборах вырезов в древовидной структуре; доказательство гипотезы Вагнера что в любом бесконечном множестве графов один из них является минором другого (и, следовательно, любое свойство графов, которое может характеризоваться исключёнными минорами, может характеризоваться конечным списком исключённых миноров); доказательство подобной гипотезы Нэша-Уильямса о том, что в любом бесконечном множестве графов один из них может быть погружен в другой; алгоритмы полиномиального времени, чтобы проверить, содержит ли граф фиксированный граф в качестве минора, и решить проблему к вершинно-непересекающихся путей для всех фиксированных k.

Примерно в 1990 году Робин Томас начал работать с Робертсоном и Сеймуром. В результате их сотрудничества в течение следующих десяти лет было подготовлено несколько важных совместных статей: доказательство гипотезы Сакса, характеризующей исключёнными минорами графы, допускающие бессвязные вложения в 3-пространстве; доказательство того, что каждый граф, который не является пятицветным, имеет полный граф с шестью вершинами в качестве второстепенного (предполагается, что теорема о четырёх цветах даёт этот результат, что является случаем гипотезы Хадвигера); с Дэном Сандерсом новое, упрощенное, компьютерное доказательство четырёхцветной теоремы; описание двудольных графов, допускающих пфаффиан ориентации; и приведение к почти плоскому случаю гипотезы Татта о том, что каждый кубический граф без моста, который не является трёхкратным, содержит граф Петерсена как минор. (Оставшийся «почти плоский случай» впоследствии был разрешён, тем самым получено полное доказательство гипотезы Татта; решение не использует теорему о четырёх цветах, и, более того, доказывает её в расширенной форме).

В 2000 году трио было поддержано Американским институтом математики для работы над сильной гипотезой идеального графа — открытой проблемой, поднятой Клодом Бержем в начале 1960-х годов. Студентка Сеймура Мария Чудновска присоединилась к группе в 2001 году, а в 2002 году четвёрка совместно доказала гипотезу. Сеймур продолжал работать с Чудновской и получил ещё несколько результатов о индуцированных подграфах, в частности (с тремя соавторами) алгоритм полиномиального времени для проверки того, является ли граф совершенным, и общее описание всех графов без клешней. Теорема Робертсона — Сеймура — результат, полученный в 2004 году на базе работ «проекта графовых миноров», устанавливающий вполне квазиупорядоченность множества неориентированных графов с отношением минорности.

В 2010-е годы в серии работ с Алексом Скоттом и частично с Чудновской, доказано две гипотезы Андраша Дьярфаша, что каждый граф с ограниченным числом клики и достаточно большим хроматическим числом имеет индуцированный цикл нечётной длины не менее пяти и имеет индуцированный цикл длины не менее любого указанного числа.

В конце 2010-х и начале 2020-х годов исследования Сеймура были в значительной степени сосредоточены на гипотезе Эрдёша — Хайнала^[12]. В 2019 году в соавторстве с Марией Чудновской, Джейкобом Фоксом, Алексом Скоттом и Софи Спиркл была опубликована работа «На пути к гипотезе Эрдёша — Хайнала для графов без 5-дыр»^[13]. Это привело к значительному прорыву в 2020 году, когда Сеймур, Чудновская, Скотт и Спиркл доказали, что гипотеза верна для графов, не содержащих в качестве индуцированного подграфа цикл из пяти вершин (C5)^[14]. Работа в этом направлении продолжилась, и в 2023 году Сеймур совместно с соавторами представил дальнейшее продвижение в решении общей проблемы^[15]. Среди других недавних результатов — построение контрпримера к грубой гипотезе Менгера (2024, совместно с Тунгом Нгуеном и Алексом Скоттом)^[16] и публикация ряда работ, посвящённых структуре турниров и графов с запрещёнными индуцированными подграфами^[17][13].