Пол Сеймур (математик)
британский математик

Пол Сеймур
ФРС
Сеймур в Обервольфахе в 2016 году
Рожденный( 1950-07-26 )26 июля 1950 г. (74 года)
Плимут , Девон, Англия
Национальностьбританский
Альма-матерОксфордский университет (бакалавр, доктор философии)
НаградыСтипендия Слоуна (1983)
Премия Островского (2003)
Премия Джорджа Полиа (1983, 2004)
Премия Фулкерсона (1979, 1994, 2006, 2009)
Научная карьера
УчрежденияПринстонский университет
Беллкорский
университет Ватерлоо
Ратгерский университет
Университет штата Огайо
научный руководительОбри Уильям Инглтон
ДокторантыМария Чудновская
Санг-иль Ум

Пол Д. Сеймур ( родился 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]

Сеймур выступает с речью в 2010 году

Личная жизнь

Он женился на Шелли Макдональд из Оттавы в 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]

Избранные публикации

  1. ^ Сеймур, ПД (1977). «Матроиды со свойством максимального потока и минимального разреза». Журнал комбинаторной теории, серия B. 23 ( 2–3): 189–222. doi : 10.1016/0095-8956(77)90031-4 .
  2. ^ Сеймур, П.Д. (1978). "Матроиды представимы более ". Комбинированные проблемы и теория графов (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) . Коллок. Интерн. CNRS. 260 : 381–383. Г Ф ( 3 ) {\displaystyle {\rm {GF}}(3)}
  3. ^ Сеймур, ПД (1980). «Разложение регулярных матроидов». Журнал комбинаторной теории, Серия B. 28 ( 3): 305–359. doi :10.1016/0095-8956(80)90075-1.
  4. ^ Сеймур, PD; Уэлш, DJA (1978). «Вероятности просачивания на квадратной решетке». Annals of Discrete Mathematics . 3 : 227–245. doi :10.1016/S0167-5060(08)70509-0. ISBN 9780720408430.
  5. ^ Сеймур, ПД (1979). «О многоцветных кубических графах и гипотезах Фулкерсона и Тутта». Труды Лондонского математического общества . 3 (3): 423–460. doi :10.1112/plms/s3-38.3.423.
  6. ^ Сеймур, ПД (1981). «Нигде-ноль 6-потоки». Журнал комбинаторной теории, Серия B. 30 ( 2): 130–135. doi : 10.1016/0095-8956(81)90058-7 .
  7. ^ Сеймур, ПД (1980). «Непересекающиеся пути в графах». Дискретная математика . 29 (3): 293–309. doi :10.1016/0012-365X(80)90158-2.
  8. ^ Робертсон, Н.; Сеймур, П. (1999). «Миноры графа. XVII. Укрощение вихря». Журнал комбинаторной теории, Серия B. 77 ( 1): 162–210. doi : 10.1006/jctb.1999.1919 .
  9. ^ Робертсон, Н.; Сеймур, П. (2004). «Миноры графа. XX. Гипотеза Вагнера». Журнал комбинаторной теории, Серия B. 92 ( 2): 325–357. doi : 10.1016/j.jctb.2004.08.001 .
  10. ^ Робертсон, Н.; Сеймур, П. (2010). «Миноры графа XXIII. Гипотеза погружения Нэша-Вильямса». Журнал комбинаторной теории, серия B. 100 ( 2): 181–205. CiteSeerX 10.1.1.304.8831 . doi : 10.1016/j.jctb.2009.07.003 . 
  11. ^ Робертсон, Н.; Сеймур, П. (1995). «Миноры графа. XIII. Проблема непересекающихся путей». Журнал комбинаторной теории, Серия B. 63 ( 1): 65–110. doi : 10.1006/jctb.1995.1006 .
  12. ^ Робертсон, Н .; Сеймур, П.; Томас, Р. (1995). «Гипотеза Сакса о бессвязном вложении». Журнал комбинаторной теории, Серия B. 64 ( 2): 185–227. doi : 10.1006/jctb.1995.1032 .
  13. ^ Робертсон, Н.; Сеймур, П.; Томас, Р. (1993). «Гипотеза Хадвигера для -свободных графов». Combinatorica . 13 (3): 279–361. doi :10.1007/BF01202354. S2CID  9608738. К 6 {\displaystyle К_{6}}
  14. ^ Робертсон, Н .; Сандерс, Д.; Сеймур, П.; Томас, Р. (1997). «Теорема о четырех цветах». Журнал комбинаторной теории, Серия B. 70 ( 1): 2–44. doi : 10.1006/jctb.1997.1750 .
  15. ^ Робертсон, Н.; Сеймур, П.; Томас, Р. (1999). «Перманенты, ориентации Пфаффа и даже направленные контуры». Annals of Mathematics . 150 (3): 929–975. arXiv : math/9911268 . doi :10.2307/121059. JSTOR  121059. S2CID  7489315.
  16. ^ Алон, Н.; Сеймур, П.; Томас, Р. (1990). «Теорема о разделителе для непланарных графов». Журнал Американского математического общества . 3 (4): 801–808. doi : 10.2307/1990903 . JSTOR  1990903.
  17. ^ Сеймур, П.; Томас, Р. (1993). «Поиск графа и теорема о минимуме-максимуме для ширины дерева». Журнал комбинаторной теории, Серия B. 58 ( 1): 22–33. doi : 10.1006/jctb.1993.1027 .
  18. ^ Сеймур, П.; Томас, Р. (1994). «Маршрутизация вызовов и крысолов». Combinatorica . 14 (2): 217–241. doi :10.1007/BF01215352. S2CID  7508434.
  19. ^ Чудновский, М .; Робертсон, Н .; Сеймур, П.; Томас, Р. (2006). «Сильная теорема о совершенном графе». Annals of Mathematics . 164 (1): 51–229. arXiv : math/0212070 . doi : 10.4007/annals.2006.164.51 . S2CID  119151552.
  20. ^ Чудновский, М .; Корнюжоль, Ж ; Лю, X.; Сеймур, П.; Вушкович, К. (2005). «Распознавание графов Берге». Комбинаторика . 25 (2): 143–186. дои : 10.1007/s00493-005-0012-8. S2CID  2229369.
  21. ^ Чудновский, М. ; Сеймур, П. (2008). «Графы без клешней. V. Глобальная структура». Журнал комбинаторной теории, Серия B . 98 (6): 1373–1410. CiteSeerX 10.1.1.125.1835 . doi : 10.1016/j.jctb.2008.03.002 . 
  22. ^ Oum, S. ; Seymour, P. (2006). «Аппроксимация ширины клики и ширины ветви». Журнал комбинаторной теории, серия B . 96 (4): 514–528. CiteSeerX 10.1.1.139.9829 . doi : 10.1016/j.jctb.2005.10.006 . 
  23. ^ Чудновский, М.; Сеймур, П. (2007). «Корни полинома независимости графа без клешней». Журнал комбинаторной теории, серия B. 97 ( 3): 350–357. CiteSeerX 10.1.1.118.3609 . doi : 10.1016/j.jctb.2006.06.001 . 
  24. ^ Скотт, А.; Сеймур, П. (2016). «Индуцированные подграфы графов с большим хроматическим числом. I. Нечетные дыры». Журнал комбинаторной теории, серия B. 121 : 68–86. arXiv : 1410.4118 . doi : 10.1016 /j.jctb.2015.10.002 . S2CID  52874586.
  25. ^ Чудновский, М .; Скотт, А.; Сеймур, П. (2017). «Индуцированные подграфы графов с большим хроматическим числом. III. Длинные дыры». Combinatorica . 37 (6): 1057–1072. arXiv : 1506.02232 . doi : 10.1007/s00493-016-3467-x. S2CID  2560430.
  26. ^ Скотт, А.; Сеймур, П. (2019). «Индуцированные подграфы графов с большим хроматическим числом. X. Дыры с определенным остатком». Combinatorica . 39 (5): 1105–1132. arXiv : 1705.04609 . doi :10.1007/s00493-019-3804-y. S2CID  51746725.
  27. ^ Чудновский, М .; Скотт, А.; Сеймур, П.; Спиркл, С. (2020). «Обнаружение странной дырки». Журнал ACM . 67 (1): 12 стр. doi : 10.1145/3375720 . hdl : 10012/18527 . S2CID  119705201.
  28. ^ Чудновский, М .; Скотт, А.; Сеймур, П.; Спиркл, С. (2023). «Эрдёш–Хайнал для графов без 5-дырок». Труды Лондонского математического общества . 126 (3): 997–1014. arXiv : 2102.04994 . doi : 10.1112/plms.12504. S2CID  259380697.

Смотрите также

Ссылки

  1. ^ Сеймур, Пол. "Online Papers" . Получено 26 апреля 2013 г.
  2. ^ "Профессорство | Декан факультета".
  3. ^ Эллин Джексон. «Сеймур получает премию Островского» (PDF) . Уведомления AMS . 51 : 900.
  4. ^ "Выдающиеся ученые, избранные членами и иностранными членами Королевского общества" . Получено 11 мая 2022 г.
  5. ^ ab "Резюме Пола Сеймура" (PDF) . Получено 27 мая 2022 г. .
  6. ^ "Journal of Graph Theory Editorial Board" . Получено 27 мая 2022 г. .
  7. ^ "Редакционная коллегия Combinatorica" ​​. Получено 27 мая 2022 г. .
  8. ^ "Journal of Combinatori Theory, Series B Editorial Board" . Получено 27 мая 2022 г. .
  9. ^ "Вирус простуды поможет больным раком". 11 января 2007 г.
На Викискладе есть медиафайлы по теме Пол Сеймур (математик).
Взято с "https://en.wikipedia.org/w/index.php?title=Пол_Сеймур_(математик)&oldid=1255889285"