Пол Д. Сеймур ( родился 26 июля 1950 г.) — британский математик, известный своими работами в области дискретной математики , особенно теории графов . Он (совместно с другими) был ответственен за важный прогресс в области регулярных матроидов и полностью унимодулярных матриц , теоремы о четырёх красках , вложений без связей , миноров графов и структуры , гипотезы о совершенном графе , гипотезы Хадвигера , графов без клешней , χ-ограниченности и гипотезы Эрдёша–Хайнала . Многие из его последних работ доступны на его веб-сайте. [1]
В настоящее время Сеймур является профессором математики имени Альберта Болдуина Дода в Принстонском университете . [2] Он выиграл стипендию Слоуна в 1983 году и премию Островского в 2003 году; [3] и (иногда вместе с другими) выиграл премию Фулкерсона в 1979, 1994, 2006 и 2009 годах, а также премию Пойа в 1983 и 2004 годах. Он получил почетную докторскую степень от Университета Ватерлоо в 2008 году, одну от Технического университета Дании в 2013 году и одну от Высшей нормальной школы Лиона в 2022 году. Он был приглашенным докладчиком на Международном конгрессе математиков 1986 года и пленарным докладчиком на Международном конгрессе математиков 1994 года . В 2022 году он стал членом Королевского общества. [4]
Сеймур родился в Плимуте , Девон, Англия. Он был дневным студентом в Плимутском колледже , а затем учился в Эксетер-колледже, Оксфорд , получив степень бакалавра в 1971 году и доктора философии в 1975 году.
С 1974 по 1976 год он был научным сотрудником колледжа в Университетском колледже Суонси , а затем вернулся в Оксфорд на 1976–1980 годы в качестве младшего научного сотрудника в Мертон-колледже, Оксфорд , с 1978 по 1979 год в Университете Ватерлоо . [5] Он стал ассоциированным, а затем полным профессором в Университете штата Огайо , Колумбус, Огайо , между 1980 и 1983 годами, где он начал исследования с Нилом Робертсоном , плодотворное сотрудничество, которое продолжалось в течение многих лет. С 1983 по 1996 год он работал в Bellcore (Bell Communications Research), Морристаун, Нью-Джерси (теперь Telcordia Technologies ). Он также был приглашенным профессором в Университете Ратгерса с 1984 по 1987 год и в Университете Ватерлоо с 1988 по 1993 год. Он стал профессором Принстонского университета в 1996 году. [5] Он является главным редактором (совместно с Карстеном Томассеном ) журнала Journal of Graph Theory , [6] и редактором журналов Combinatorica [7] и Journal of Combinatori Theory, Series B. [ 8]
Он женился на Шелли Макдональд из Оттавы в 1979 году, и у них двое детей, Эми и Эмили. Пара рассталась полюбовно в 2007 году. [ необходима цитата ] Его брат Леонард В. Сеймур — профессор генной терапии в Оксфордском университете . [9]
В комбинаторике Оксфорда в 1970-х годах доминировала теория матроидов из-за влияния Доминика Уэлша и Обри Уильяма Инглтона . Большая часть ранних работ Сеймура, примерно до 1980 года, была посвящена теории матроидов и включала три важных результата по матроидам: его докторская диссертация о матроидах со свойством максимального потока и минимального разреза [pub 1] (за которую он получил свою первую премию Фулкерсона); характеристика исключенными минорами матроидов, представимых над трехэлементным полем; [pub 2] и теорема о том, что все регулярные матроиды состоят из графических и кографических матроидов, соединенных вместе простым способом [pub 3] (за которую он получил свою первую премию Пойя). Было несколько других значимых работ этого периода: статья с Уэлшем о критических вероятностях для просачивания связей на квадратной решетке; [pub 4] статья о многоцветной раскраске ребер кубических графов, [pub 5] которая предвосхищает теорему Ласло Ловаса о решетке соответствий ; статья, доказывающая, что все графы без мостов допускают нигде не нулевые 6-потоки, [pub 6] шаг к гипотезе Тутта о нигде не нулевых 5-потоках ; и статья, решающая задачу о двух путях (также вводящая гипотезу о двойном покрытии циклов ), [pub 7], которая стала движущей силой многих будущих работ Сеймура.
В 1980 году он перешел в Университет штата Огайо и начал работать с Нилом Робертсоном. Это в конечном итоге привело к самому важному достижению Сеймура, так называемому «Проекту миноров графа», серии из 23 статей (совместно с Робертсоном), опубликованных в течение следующих тридцати лет, с несколькими значительными результатами: теорема о структуре миноров графа , что для любого фиксированного графа все графы, которые не содержат его как минор, могут быть построены из графов, которые по существу имеют ограниченный род, путем объединения их вместе в небольших сечениях в древовидной структуре; [pub 8] доказательство гипотезы Вагнера о том, что в любом бесконечном наборе графов один из них является минором другого (и, следовательно, что любое свойство графов, которое может быть охарактеризовано исключенными минорами, может быть охарактеризовано конечным списком исключенных миноров); [pub 9] доказательство аналогичной гипотезы Нэша-Вильямса о том, что в любом бесконечном наборе графов один из них может быть погружен в другой; [pub 10] и алгоритмы полиномиального времени для проверки того, содержит ли граф фиксированный граф в качестве минора, и для решения задачи о k вершинно-непересекающихся путях для всех фиксированных k. [pub 11]
Около 1990 года Робин Томас начал работать с Робертсоном и Сеймуром. Их сотрудничество привело к нескольким важным совместным работам в течение следующих десяти лет: доказательство гипотезы Сакса , характеризующее исключенными минорами графы, которые допускают вложения без зацеплений в 3-пространство; [pub 12] доказательство того, что каждый граф, который не является пятицветным, имеет шестивершинный полный граф в качестве минора (предполагается, что теорема о четырех красках дает этот результат, что является случаем гипотезы Хадвигера ); [pub 13] с Дэном Сандерсом , новое, упрощенное, основанное на компьютере доказательство теоремы о четырех красках ; [pub 14] и описание двудольных графов, которые допускают пфаффовские ориентации . [pub 15] В тот же период Сеймур и Томас также опубликовали несколько важных результатов: (совместно с Ногой Алоном ) теорему о разделителе для графов с исключенным минором, [pub 16] расширяющую теорему о плоском разделителе Ричарда Липтона и Роберта Тарьяна ; статью, характеризующую ширину дерева в терминах ежевики ; [pub 17] и алгоритм полиномиального времени для вычисления ширины ветвей плоских графов. [pub 18]
В 2000 году Робертсон, Сеймур и Томас получили поддержку Американского института математики для работы над сильной гипотезой о совершенном графе , известным открытым вопросом, который был поднят Клодом Берже в начале 1960-х годов. Студентка Сеймура Мария Чудновски присоединилась к ним в 2001 году, и в 2002 году четверо совместно доказали гипотезу. [pub 19] Сеймур продолжил работать с Чудновски и получил еще несколько результатов об индуцированных подграфах, в частности (совместно с Корнуэжолем , Лю и Вушковичем ) полиномиальный алгоритм для проверки того, является ли граф совершенным, [pub 20] и общее описание всех графов без клешней. [pub 21] Другие важные результаты этого периода включают: (совместно со студентом Сеймура Санг-Илом Умом ) фиксированно-параметрические разрешимые алгоритмы для аппроксимации кликовой ширины графов (в пределах экспоненциальной границы) и ветвевой ширины матроидов (в пределах линейной границы); [pub 22] и (совместно с Чудновским) доказательство того, что корни полинома независимости любого графа без клешней являются действительными. [pub 23]
В 2010-х годах Сеймур работал в основном над χ-ограниченностью и гипотезой Эрдёша–Хайнала . В серии статей с Алексом Скоттом и частично с Чудновским они доказали две гипотезы Андраша Дьярфаша о том, что любой граф с ограниченным кликовым числом и достаточно большим хроматическим числом имеет индуцированный цикл нечетной длины не менее пяти [pub 24] и имеет индуцированный цикл длины не менее любого указанного числа [pub 25] Серия достигла кульминации в статье Скотта и Сеймура, доказывающей, что для любого фиксированного k любой граф с достаточно большим хроматическим числом содержит либо большой полный подграф, либо индуцированные циклы всех длин по модулю k [pub 26], что приводит к разрешению двух гипотез Гила Калаи и Роя Мешулама, связывающих хроматическое число графа с гомологией его комплекса независимости . Также был разработан полиномиальный алгоритм (совместно с Чудновским, Скоттом и Чудновским и ученицей Сеймура Софи Спиркл) для проверки того, содержит ли граф индуцированный цикл с длиной больше трех и нечетной. [pub 27] Совсем недавно четверо совместно разрешили случай 5-цикла гипотезы Эрдёша–Хайнала, которая гласит, что каждый граф без индуцированной копии 5-цикла содержит независимое множество или клику полиномиального размера. [pub 28]
