✖


Jump to content

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

Пол Сеймур
ФРС
Рожденный ( 1950-07-26 ) 26 июля 1950 г. (73 года)
Плимут , Девон, Англия
Национальность Британский
Альма-матер Оксфордский университет (бакалавр, доктор философии)
Награды Стипендия Слоана (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–79 годах — в Университете Ватерлоо . [5] В период с 1980 по 1983 год он стал доцентом, а затем и профессором штата Огайо Университета в Колумбусе, штат Огайо , где начал исследования вместе с Нилом Робертсоном .плодотворное сотрудничество, продолжавшееся многие годы. С 1983 по 1996 год он работал в Bellcore (Bell Communications Research), Морристаун, Нью-Джерси (ныне Telcordia Technologies ). Он также был адъюнкт-профессором в Университете Рутгерса с 1984 по 1987 год и в Университете Ватерлоо с 1988 по 1993 год. В 1996 году он стал профессором Принстонского университета . [5] Он является главным редактором (совместно с Карстеном Томассеном ) журнала Journal of Graph Theory . [6] и редактор Combinatorica [7] и Журнал комбинаторной теории, серия B. [8]

Пол Сеймур в 2007 году
(фото из МФО)

Личная жизнь [ править ]

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

Основные вклады [ править ]

В комбинаторике в Оксфорде в 1970-е годы доминировала теория матроидов , благодаря влиянию Доминика Уэлша и Обри Уильяма Инглтона . Большая часть ранних работ Сеймура, примерно до 1980 года, была посвящена теории матроидов и включала три важных результата по матроидам: его докторскую степень. диссертация по матроидам со свойством max-flow min-cut [паб 1] (за что он выиграл свою первую премию Фулкерсона); характеристика исключенными минорами матроидов, представимых в трехэлементном поле; [паб 2] и теорема о том, что все регулярные матроиды состоят из графических и кографических матроидов, простым образом соединенных вместе. [паб 3] (который выиграл его первую премию Полиа). Было еще несколько важных статей этого периода: статья с Уэлшем о критических вероятностях перколяции связей в квадратной решетке; [паб 4] статья о раскраске ребер кубических графов, [паб 5] что предвещает теорему Ласло Ловаса о согласованной решетке ; статья, доказывающая, что все графы без мостов допускают нигде ненулевые 6-потоки, [паб 6] шаг к гипотезе Тутте о пяти потоках, где нигде нет нуля ; и статья, решающая проблему двух путей (также представляющая гипотезу о двойном покрытии цикла ), [паб 7] который стал двигателем большей части будущей работы Сеймура.

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

Примерно в 1990 году Робин Томас начал работать с Робертсоном и Сеймуром. Результатом их сотрудничества в течение следующих десяти лет стало несколько важных совместных документов:доказательство гипотезы Сакса , характеризующей исключенными минорами графы, допускающие бесзвенные вложения в 3-пространство; [паб 12] доказательство того, что каждый граф, который не является пятицветным, имеет полный граф с шестью вершинами в качестве минора (предполагается, что теорема о четырех цветах дает этот результат, что является случаем гипотезы Хадвигера ); [паб 13] с Дэном Сандерсом , новым, упрощенным, компьютерным доказательством теоремы о четырех цветах ; [паб 14] и описание двудольных графов, допускающих пфаффову ориентацию . [паб 15] В тот же период Сеймур и Томас также опубликовали несколько важных результатов: (совместно с Ногой Алоном ) теорему о разделителе для графов с исключенным минором, [паб 16] расширение о плоском сепараторе и теоремы Ричарда Липтона Роберта Тарьяна ; бумага, характеризующая ширину дерева в единицах ежевики ; [паб 17] и алгоритм с полиномиальным временем для вычисления ширины ветвей планарных графов. [паб 18]

поддержал Робертсона, Сеймура и Томаса В 2000 году Американский институт математики в работе над гипотезой сильного совершенного графа — знаменитым открытым вопросом, который был поднят Клодом Берже в начале 1960-х годов. Ученица Сеймура Мария Чудновская присоединилась к ним в 2001 году, а в 2002 году все четверо совместно доказали гипотезу. [паб 19] Сеймур продолжал работать с Чудновским и получил еще несколько результатов о индуцированных подграфах, в частности (совместно с Корнюжолем , Лю и Вушковичем ) алгоритм с полиномиальным временем для проверки того, является ли граф совершенным, [паб 20] и общее описание всех графов без когтей. [паб 21] Другие важные результаты этого периода включают: (совместно с учеником Сеймура Санг-ил Оумом ) с фиксированными параметрами управляемые алгоритмы для аппроксимации ширины клики графов (в пределах экспоненциальной границы) и ширины ветвей матроидов (в пределах линейной границы); [паб 22] и (совместно с Чудновским) доказательство того, что корни полинома независимости любого графа без когтей вещественны. [паб 23]

В 2010-х годах Сеймур работал в основном над χ-ограниченностью и гипотезой Эрдеша-Хайнала . В серии статей с Алексом Скоттом и частично с Чудновским они доказали две гипотезы Андраша Дьярфаса о том, что каждый граф с ограниченным кликовым числом и достаточно большим хроматическим числом имеет индуцированный цикл нечетной длины не менее пяти, [паб 24] и имеет индуцированный цикл длиной не менее любого заданного числа. [паб 25] Кульминацией этой серии стала статья Скотта и Сеймура, доказывающая, что для каждого фиксированного k каждый граф с достаточно большим хроматическим числом содержит либо большой полный подграф, либо индуцированные циклы всех длин по модулю k: [паб 26] что приводит к разрешению двух гипотез Гила Калаи и Роя Мешулама, связывающих хроматическое число графа с гомологиями его комплекса независимости . Существовал также алгоритм с полиномиальным временем (с Чудновским, Скоттом, Чудновским и ученицей Сеймура Софи Спиркл) для проверки того, содержит ли граф индуцированный цикл длиной более трех и нечетный. [паб 27] Совсем недавно все четверо совместно разрешили случай 5-цикла гипотезы Эрдеша-Хайнала, которая гласит, что каждый граф без индуцированной копии 5-цикла содержит независимый набор или клику полиномиального размера. [паб 28]

Избранные публикации [ править ]

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

См. также [ править ]

Ссылки [ править ]

  1. ^ Сеймур, Пол. «Интернет-документы» . Проверено 26 апреля 2013 г.
  2. ^ «Профессора | Декан факультета» .
  3. ^ Эллин Джексон. «Сеймур получает премию Островского» (PDF) . Уведомления АМС . 51 :900.
  4. ^ «Выдающиеся ученые избраны научными сотрудниками и иностранными членами Королевского общества» . Проверено 11 мая 2022 г.
  5. ↑ Перейти обратно: Перейти обратно: а б «Резюме Пола Сеймура» (PDF) . Проверено 27 мая 2022 г.
  6. ^ «Журнал редакционной коллегии теории графов» . Проверено 27 мая 2022 г.
  7. ^ «Редакция Комбинаторики» . Проверено 27 мая 2022 г.
  8. ^ «Журнал комбинаторной теории, серия Б, редакционная коллегия» . Проверено 27 мая 2022 г.
  9. ^ «Вирус простуды в помощь онкологическим больным» . 11 января 2007 г.

Внешние ссылки [ править ]

Викискладе есть медиафайлы, связанные с Полом Сеймуром (математиком) .
Retrieved from "https://en.wikipedia.org/w/index.php?title=Paul_Seymour_(mathematician)&oldid=1222918233"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: d3845f3164c285dc41703e654809b58e__1715183940
URL1:https://arc.ask3.ru/arc/aa/d3/8e/d3845f3164c285dc41703e654809b58e.html
Заголовок, (Title) документа по адресу, URL1:
Paul Seymour (mathematician) - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)