Пол Сеймур (математик) - Paul Seymour (mathematician)
Пол Сеймур | |
|---|---|
 | |
| Родился |
26 июля 1950 г.
Плимут , Девон, Англия
|
| Национальность | Британский |
| Альма-матер | Оксфордский университет (бакалавр, доктор философии) |
| Награды |
Стипендия Слоуна (1983) Премия Островского (2003) Премия Джорджа Полиа (1983, 2004) Премия Фулкерсона (1979, 1994, 2006, 2009) |
| Научная карьера | |
| Учреждения |
Принстонский университет Bellcore University of Waterloo Rutgers University Государственный университет Огайо |
| Докторант | Обри Уильям Инглтон |
| Докторанты |
Мария Чудновская Sang-il Oum |
Пол Д. Сеймур (родился 26 июля 1950 г.) - британский математик, известный своими работами в области дискретной математики , особенно теории графов . Он (вместе с другими) отвечал за важный прогресс в области регулярных матроидов и полностью унимодулярных матриц , теоремы о четырех цветах , вложений без звеньев , миноров и структуры графов, гипотезы об идеальном графе, гипотезы Хадвигера , графов без клешней , χ-ограниченности и Erdős-Hajnal гипотеза . Многие из его последних работ доступны на его веб-сайте.
Сеймур в настоящее время является профессором математики Альберта Болдуина Дода в Принстонском университете . Он выиграл стипендию Слоуна в 1983 году и премию Островского в 2004 году; и (иногда вместе с другими) выигрывал премию Фулкерсона в 1979, 1994, 2006 и 2009 годах, а также премию Полиа в 1983 и 2004 годах. Он получил почетную докторскую степень в Университете Ватерлоо в 2008 году и одну из Технического университета Дании в 2013 году. Он был приглашенным докладчиком на Международном конгрессе математиков 1986 года и пленарным докладчиком на Международном конгрессе математиков 1994 года .
Ранние годы
Сеймур родился в Плимуте , Девон, Англия. Он был дневным студентом Плимутского колледжа , а затем учился в Эксетер-колледже в Оксфорде , получив степень бакалавра в 1971 году и докторскую степень в 1975 году.
Карьера
С 1974 по 1976 год он был научным сотрудником университетского колледжа Суонси , а затем вернулся в Оксфорд в 1976–1980 годах в качестве младшего научного сотрудника в Мертон-колледже, Оксфорд , а в 1978–79 годах - в Университете Ватерлоо . В период с 1980 по 1983 год он стал младшим научным сотрудником, а затем профессором в Университете штата Огайо , Колумбус, штат Огайо , где он начал исследования с Нилом Робертсоном , плодотворное сотрудничество, которое продолжалось много лет. С 1983 по 1996 год он работал в Bellcore (Bell Communications Research), Морристаун, Нью-Джерси (ныне Telcordia Technologies ). Он также был адъюнкт-профессором в Университете Рутгерса с 1984 по 1987 год и в Университете Ватерлоо с 1988 по 1993 год. Он стал профессором Принстонского университета в 1996 году. Он является главным редактором (совместно с Карстеном Томассеном ) журнала Journal of Теория графов и редактор для Combinatorica и журнала комбинаторной теории, серии B .
Личная жизнь
Он женился на Шелли Макдональд из Оттавы в 1979 году, и у них двое детей, Эми и Эмили. Пара полюбовно рассталась в 2007 году. Его брат Леонард Сеймур - профессор генной терапии в Оксфордском университете .
Основные вклады
Комбинаторика в Оксфорде в 1970-х годах находилась под влиянием теории матроидов из-за влияния Доминика Уэлша и Обри Уильяма Инглтона . Большая часть ранних работ Сеймура, примерно до 1980 г., была посвящена теории матроидов и включала три важных результата по матроидам: его докторскую диссертацию. диссертация по матроидам со свойством max-flow min-cut (за что он получил свою первую премию Фулкерсона); характеристика исключенными минорами матроидов, представимых над трехэлементным полем; и теорема о том, что все обычные матроиды состоят из графических и кографических матроидов, соединенных вместе простым способом (которая выиграла его первую премию Полиа). В этот период было несколько других значительных работ: статья с валлийским языком о критических вероятностях перколяции связей на квадратной решетке; статья, в которой была введена гипотеза о циклическом двойном покрытии ; статья о красках кубических графов, которая предвосхищает теорему Ласло Ловаса о решетке согласования ; статья, доказывающая, что все графы без мостов допускают нигде-нулевые 6-потоки, шаг к гипотезе Тутте о 5-потоках, нигде не нулевых ; и документ, решающий проблему двух путей, которая была движущей силой большей части будущей работы Сеймура.
В 1980 году он перешел в Государственный университет Огайо и начал работать с Нилом Робертсоном. В конечном итоге это привело к самому важному достижению Сеймура, так называемому "Graph Minors Project", серии из 23 статей (совместно с Робертсоном), опубликованных в течение следующих тридцати лет, с несколькими важными результатами: теорема о структуре миноров графа , которая для любой фиксированный граф, все графы, которые не содержат его в качестве второстепенного, могут быть построены из графов, которые по существу имеют ограниченный род, путем соединения их вместе в небольших наборах в древовидной структуре; доказательство гипотезы Вагнера о том, что в любом бесконечном множестве графов один из них является второстепенным по отношению к другому (и, следовательно, любое свойство графов, которое может быть охарактеризовано исключенными минорами, может быть охарактеризовано конечным списком исключенных миноров); доказательство аналогичной гипотезы Нэша-Вильямса о том, что в любом бесконечном множестве графов один из них может быть погружен в другой; и алгоритмы с полиномиальным временем, чтобы проверить, содержит ли граф фиксированный граф в качестве второстепенного, и решить проблему k вершинно-непересекающихся путей для всех фиксированных k.
Примерно в 1990 году Робин Томас начал работать с Робертсоном и Сеймуром. Их сотрудничество привело к появлению нескольких важных совместных работ в течение следующих десяти лет: доказательство гипотезы Сакса , характеризующей исключенными минорами графы, допускающие вложения без зацеплений в 3-пространство; доказательство того, что каждый граф, который не является пятицветным, имеет шестивершинный полный граф как минор (предполагается, что для получения этого результата используется теорема о четырех цветах, что является случаем гипотезы Хадвигера ); с Дэном Сандерсом - новое упрощенное компьютерное доказательство теоремы о четырех цветах ; и описание двудольных графов, допускающих пфаффову ориентацию . В тот же период Сеймур и Томас также опубликовали несколько важных результатов: (вместе с Ногой Алон ) теорему о разделителе для графов с исключенным второстепенным, расширяющую теорему о плоском разделителе Ричарда Липтона и Роберта Тарьяна ; бумага, характеризующая ширину дерева в терминах ежевики ; и алгоритм с полиномиальным временем для вычисления ширины ветвления плоских графов.
В 2000 году Американский институт математики поддержал Робертсона, Сеймура и Томаса в работе над сильной гипотезой о совершенном графе - известным открытым вопросом, который был поднят Клодом Берже в начале 1960-х годов. Студентка Сеймура Мария Чудновская присоединилась к ним в 2001 году, а в 2002 году все четверо совместно доказали гипотезу. Сеймур продолжал работать с Чудновским и получил еще несколько результатов об индуцированных подграфах, в частности (с Корнежолем , Лю, Вусковичем) алгоритм с полиномиальным временем для проверки совершенства графа и общее описание всех графов без когтей. Другие важные результаты этого периода включают: (со студентом Сеймура Санг-ил Оум ) управляемые алгоритмы с фиксированными параметрами для аппроксимации ширины клики графов (в пределах экспоненциальной границы) и ширины ветвления матроидов (в пределах линейной границы); и (вместе с Чудновским) доказательство того, что корни полинома независимости любого графа без клешней вещественны.
В 2010-х Сеймур работал в основном над χ-ограниченностью и гипотезой Эрдеша – Хайнала . В серии работ с Алексом Скоттом и частично с Чудновским они доказали две гипотезы Андраша Дьярфаша о том , что каждый граф с ограниченным кликовым числом и достаточно большим хроматическим числом имеет индуцированный цикл нечетной длины не менее пяти и индуцированный цикл размером длина не менее любого указанного числа. Кульминацией серии стала работа Скотта и Сеймура, в которой доказано, что для любого фиксированного k каждый граф с достаточно большим хроматическим числом содержит либо большой полный подграф, либо индуцированные циклы любой длины по модулю k, что приводит к разрешению двух гипотез Гила Калаи. и Рой Мешулам, связывающий хроматическое число графа с гомологиями его комплекса независимости . Был также алгоритм с полиномиальным временем (с Чудновским, Скоттом, Чудновским и ученицей Сеймура Софи Спиркл) для проверки того, содержит ли граф индуцированный цикл с длиной более трех и нечетным. Совсем недавно эти четверо совместно разрешили пятицикловый случай гипотезы Эрдеша – Хайнала, согласно которой каждый граф без индуцированной копии 5-цикла содержит независимое множество или клику полиномиального размера.
Смотрите также
использованная литература
внешние ссылки
- Домашняя страница Пола Сеймура в Принстонском университете
- Пол Сеймур на проекте « Математическая генеалогия»