Seymour, Paul (matematik)

Stabilní verze byla odhlášena 4. ledna 2022 . Existují neověřené změny v šablonách nebo .
Paul Seymour
Datum narození 26. července 1950 (ve věku 72 let)( 1950-07-26 )
Místo narození Plymouth , Anglie
Země
Vědecká sféra kombinatorika a teorie grafů
Místo výkonu práce Univerzita Princeton
Alma mater
vědecký poradce Aubrey William Ingleton
Ocenění a ceny Ostrovského cena (2003)
Cena Poya (SIAM) (2004)

Paul Seymour (* 26. července 1950, Plymouth , Velká Británie ) je britský a americký matematik , profesor na Princetonské univerzitě, specialista na teorii grafů . Udělal velký příspěvek ke studiu regulárních matroidů a zcela unimodulárních matic , teorému o čtyřech barvách , nespojeného vnoření , teorému grafu , hypotézy ideálního grafu , Hadwigerovy domněnky a grafů bez drápů .

Sloan Scholar (1983), vítěz Ostrovského ceny (2004), Fulkersonovy ceny (1979, 1994, 2006, 2009), Poya Prize (1983, 2004), čestný doktorát z University of Waterloo (2008), Dánská technická univerzita ( 2013). Šéfredaktor (s Carstenem Thomassenem) Journal of Graph Theory .

Životopis

Studoval na Plymouth College a poté na Exeter College v Oxfordu, kde v roce 1971 získal titul BA a v roce 1975 doktorát .

V letech 1974 až 1976 působil jako vysokoškolský pracovník na University College Swansea . Poté se vrátil do Oxfordu, kde působil v letech 1976-1980 jako junior stipendista na Merton College a v letech 1978-1979 na University of Waterloo . V letech 1980-1983 byl mimořádným profesorem a poté profesorem na Ohio State Research University v Columbusu , kde zahájil výzkum s Neilem Robertsonem, plodnou spolupráci, která pokračovala po mnoho let. Od roku 1983 do roku 1996 pracoval v Bellcore (Bell Communications Research, nyní Telcordia Technologies) v Morristownu . Byl také mimořádným profesorem na Rutgers University v letech 1984-1987 a na University of Waterloo v letech 1988-1993. V roce 1996 se stal profesorem na Princetonské univerzitě .

Rodina

V roce 1979 se oženil s Shelley MacDonald z Ottawy a mají dvě děti, Amy a Emily. Pár se rozešel v roce 2007. Bratr - Linord Seymour -- profesor genové terapie na Oxfordské univerzitě .

Vědecké příspěvky

Kombinatorika v Oxfordu v 70. letech ovládla teorii matroidů díky vlivu Dominica Welshe a Aubrey Williama Ingletona. Velká část Seymourových raných prací, až do roku 1980, se týkala teorie matroidů a zahrnovala tři důležité články o matroidech: doktorskou disertaci; článek o charakterizaci vyloučených nezletilých matroidů zastoupených na tříprvkovém poli; a teorém, že všechny pravidelné matroidy jsou složeny z grafických a kographových matroidů poskládaných jednoduchým způsobem (výsledek, za který byla udělena cena Poya). Od tohoto období bylo vydáno několik dalších významných dokumentů: článek s Welshem o kritických pravděpodobnostech úniku vazeb na čtvercové mřížce; článek, ve kterém je popsána hypotéza dvojitého cyklu; článek o hranové vícebarevnosti kubických grafů, který předznamenává Laszlo Lovasův koincidenční teorém o mřížce; článek dokazující, že všechny bezmůstkové grafy připouštějí nulové 6-tokové toky – krok k potvrzení Tuttovy domněnky o 5 tocích nikde nula a článek řešící problém dvou cest, který byl motorem velké části Seymourovy budoucí práce.

V roce 1980 se přestěhoval na Ohio State University, kde začal pracovat s Neilem Robertsonem a spolupracoval na vytvoření takzvaného „Graph Minor Project“, série 23 prací publikovaných v průběhu příštích třiceti let s několika významnými výsledky: teorém o struktura vedlejších grafů, že pro jakýkoli pevný graf lze všechny grafy, které jej neobsahují jako vedlejší, sestavit z grafů, které jsou v podstatě omezeného rodu, jejich spojením na malé sady řezů ve stromové struktuře; důkaz Wagnerovy domněnky, že v jakékoli nekonečné množině grafů je jeden z nich menší než druhý (a proto každá vlastnost grafů, kterou lze charakterizovat vyloučenými nezletilými, může být charakterizována konečným seznamem vyloučených nezletilých); důkaz podobné Nash-Williamsovy domněnky, že v libovolné nekonečné sadě grafů může být jeden z nich vložen do jiného; polynomiální časové algoritmy pro kontrolu, zda graf obsahuje pevný graf jako vedlejší, a vyřešení problému k vertex-disjunktních cest pro všechna pevná k.

Kolem roku 1990 začal Robin Thomas spolupracovat s Robertsonem a Seymourem. Jako výsledek jejich spolupráce v průběhu příštích deseti let bylo připraveno několik důležitých společných dokumentů: důkaz Sachsovy domněnky charakterizující grafy vyloučených nezletilých, které připouštějí nesouvislá vložení do 3-prostoru; důkaz, že každý graf, který není pětibarevný, má na pozadí úplný graf se šesti vrcholy (tento výsledek má dát věta o čtyřech barvách, což je případ Hadwigerovy domněnky ); s Danem Sandersem nový, zjednodušený, počítačový důkaz věty o čtyřech barvách; popis bipartitních grafů připouštějících Pfaffiánskou orientaci; a redukci na téměř plochý případ Tuttovy domněnky, že každý kubický nemůstkový graf, který není trojitý, obsahuje Petersenův graf jako vedlejší. (Zbývající „téměř plochý případ“ byl následně vyřešen, čímž byl získán úplný důkaz Tuttovy domněnky; řešení nepoužívá větu o čtyřech barvách a navíc ji dokazuje v rozšířené podobě).

V roce 2000 byla tato trojice podpořena Americkým matematickým institutem při práci na silné domněnce ideálního grafu, otevřeném problému, který nastolil Claude Berge na počátku 60. let. Seymourova studentka Maria Chudnovskaya se ke skupině připojila v roce 2001 a v roce 2002 všichni čtyři společně hypotézu potvrdili. Seymour pokračoval ve spolupráci s Chudnovskou a získal několik dalších výsledků na indukovaných podgrafech, zejména (se třemi spoluautory) polynomiální časový algoritmus pro kontrolu, zda je graf dokonalý, a obecný popis všech grafů bez drápů . Robertsonův-Seymourův teorém  je výsledek získaný v roce 2004 na základě práce „projektu graph minors“, který zakládá zcela kvazi-uspořádání množiny neorientovaných grafů s menšinovým vztahem.

V roce 2010 byly v sérii prací s Alex Scott a částečně s Chudnovskou prokázány dva domněnky Andráse Gyarfaše, že každý graf s omezeným klikovým číslem a dostatečně velkým chromatickým číslem má indukovaný cyklus o liché délce alespoň pět a má indukovaný cyklus délky alespoň libovolného specifikovaného čísla.

Poznámky

  1. ↑ Matematická genealogie  (anglicky) - 1997.

Odkazy

  Přejděte na položku Wikidata  Tematické stránky