Пол Сеймур (математик) - Paul Seymour (mathematician)

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

Пол Д. Сеймур (родился 26 июля 1950 г.) Альберт Болдуин Дод Профессор Математика в Университет Принстона.[1] Его исследовательский интерес заключается в дискретная математика, особенно теория графов. Он (вместе с другими) отвечал за прогресс в обычные матроиды и полностью унимодулярные матрицы, то теорема четырех цветов, вложения без ссылок, граф миноры и структура, то идеальный график предположение, Гипотеза Хадвигера, и графы без когтей. Многие из его недавних работ доступны на его веб-сайте.[2]

Он выиграл Sloan Fellowship в 1983 г., а Приз Островского в 2004 г .; и (иногда с другими) выиграл Премия Фулкерсона в 1979, 1994, 2006 и 2009 годах, а Pólya Prize в 1983 и 2004 годах. Получил степень почетного доктора Университет Ватерлоо в 2008 году и один из Технический университет Дании в 2013.

Ранние годы

Сеймур родился в Плимут, Девон, Англия. Он был студентом дневного отделения Плимутский колледж, а затем учился в Эксетерский колледж, Оксфорд, получив BA степень в 1971 году и Д. Фил в 1975 г.

Карьера

С 1974 по 1976 год он был научным сотрудником колледжа в Университетский колледж Суонси, а затем вернулся в Оксфорд в 1976–1980 гг. в качестве младшего научного сотрудника в Мертон-колледж, Оксфорд, с 1978–79 по г. Университет Ватерлоо. Он стал доцентом, а затем профессором в Государственный университет Огайо, Колумбус, Огайо, между 1980 и 1983 годами, где он начал исследования с Нил Робертсон, плодотворное сотрудничество, продолжавшееся много лет. С 1983 по 1996 год он был в Bellcore (Bell Communications Research), Морристаун, Нью-Джерси (сейчас же Telcordia Technologies ). Он также был адъюнкт-профессором в Университет Рутгерса с 1984 по 1987 год и в Университете Ватерлоо с 1988 по 1993 год. Он стал профессором Университет Принстона в 1996 г. Главный редактор (совместно с Карстен Томассен ) для Журнал теории графов.

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

Личная жизнь

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

Основные вклады

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

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

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

В 2000 году трио поддержали Американский институт математики работать над сильная гипотеза о совершенном графе, известный открытый вопрос, который был поднят Клод Берже в начале 1960-х гг. Ученица Сеймура Мария Чудновская присоединился к ним в 2001 году, а в 2002 году все четверо совместно доказали эту гипотезу. Сеймур продолжал работать с Чудновским и получил еще несколько результатов об индуцированных подграфах, в частности (с Cornuéjols, Лю, Вускович) алгоритм с полиномиальным временем для проверки совершенства графа и общее описание всех графов без клешней. Совсем недавно в серии работ с Алексом Скоттом и частично с Чудновским они доказали две гипотезы Андраш Дьярфас, что каждый граф с ограниченным кликовым числом и достаточно большим хроматическим числом имеет индуцированный цикл нечетной длины не менее пяти и индуцированный цикл длины не менее любого заданного числа.

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

использованная литература

  1. ^ https://dof.princeton.edu/about/faculty/professorships
  2. ^ Сеймур, Пол. "Интернет-газеты". Получено 26 апреля 2013.
  3. ^ http://news.bbc.co.uk/1/hi/health/6251303.stm

внешние ссылки