Seymour, Paul (matematiker)

Paul Seymour (f. 26. juli 1950, Plymouth , Storbritannien ) er en britisk og amerikansk matematiker , professor ved Princeton University, specialist i grafteori . Han ydede et stort bidrag til studiet af regulære matroider og fuldstændig unimodulære matricer , firefarvesætningen , afbrudte indlejringer , grafens mindre sætning , den ideelle grafhypotese , Hadwiger-formodningen og grafer uden kløer .

Sloan Scholar (1983), vinder af Ostrovsky-prisen (2004), Fulkerson-prisen (1979, 1994, 2006, 2009), Poya-prisen (1983, 2004), æresdoktorgrad fra University of Waterloo (2008), Danmarks Tekniske Universitet ( 2013). Ansvarshavende redaktør (med Carsten Thomassen) Journal of Graph Theory .

Biografi

Han studerede på Plymouth College og derefter på Exeter College, Oxford, og opnåede en BA i 1971 og en PhD i 1975.

Mellem 1974 og 1976 var han college-stipendiat ved University College Swansea . Han vendte derefter tilbage til Oxford, hvor han arbejdede fra 1976-1980 som juniorstipendiat ved Merton College og fra 1978-1979 ved University of Waterloo . Fra 1980-1983 var han adjungeret professor og derefter professor ved Ohio State Research University i Columbus , hvor han begyndte at forske med Neil Robertson, et frugtbart samarbejde, der fortsatte i mange år. Fra 1983 til 1996 arbejdede han hos Bellcore (Bell Communications Research, nu Telcordia Technologies) i Morristown . Han var også adjungeret professor ved Rutgers University fra 1984-1987 og ved University of Waterloo fra 1988-1993. I 1996 blev han professor ved Princeton University .

Familie

I 1979 giftede han sig med Shelley MacDonald fra Ottawa , og de har to børn, Amy og Emily. Parret gik fra hinanden i 2007. Bror-Linord Seymour-professor i genterapi ved Oxford University .

Videnskabelige bidrag

Kombinatorik i Oxford i 1970'erne dominerede matroideorien gennem indflydelse fra Dominic Welsh og Aubrey William Ingleton. Meget af Seymours tidlige arbejde, op til omkring 1980, handlede om matroideori og omfattede tre vigtige artikler om matroider: en doktorafhandling; et papir om karakterisering af de udelukkede mindreårige af matroider repræsenteret over et felt med tre elementer; og sætningen om, at alle regulære matroider er sammensat af grafiske og kografiske matroider sat sammen på en enkel måde (et resultat, som Poya-prisen blev uddelt for). Der har været adskillige andre vigtige artikler siden denne periode: et papir med walisisk om sandsynligheder for kritiske obligationslækage på et kvadratisk gitter; en artikel, hvori hypotesen om dobbeltcyklusdækning er beskrevet; en artikel om kanten multicolor af kubiske grafer, som varsler Laszlo Lovas' sammenfaldende gittersætning; et papir, der beviser, at alle broløse grafer indrømmer ingensteds-nul 6-flows – et skridt i retning af at bekræfte Tutts nowhere-zero 5-flow formodning , og et papir, der løser det to-vejs-problem, der var motoren i meget af Seymours fremtidige arbejde.

I 1980 flyttede han til Ohio State University, hvor han begyndte at arbejde sammen med Neil Robertson, og samarbejdede om at producere det såkaldte "Graph Minor Project", en serie på 23 artikler udgivet i løbet af de næste tredive år, med adskillige væsentlige resultater: en teorem om struktur af mindre grafer, at for enhver fast graf kan alle grafer, der ikke indeholder den som en mol, bygges ud fra grafer, der i det væsentlige er af begrænset slægt ved at samle dem på små sæt snit i en træstruktur; bevis for Wagners formodning om, at i ethvert uendeligt sæt af grafer, er den ene af dem en minor af den anden (og derfor kan enhver egenskab ved grafer, der kan karakteriseres ved udelukkede minorer, karakteriseres ved en finit liste over ekskluderede minor); bevis for en lignende Nash-Williams formodning om, at i ethvert uendeligt sæt af grafer, kan en af ​​dem indlejres i en anden; polynomielle tidsalgoritmer til at kontrollere, om en graf indeholder en fast graf som en minor, og løse problemet med k toppunkt-disjunkte stier for alle faste k.

Omkring 1990 begyndte Robin Thomas at arbejde sammen med Robertson og Seymour. Som et resultat af deres samarbejde over de næste ti år blev der udarbejdet adskillige vigtige fælles papirer: et bevis på Sachs-formodningen, der karakteriseres ved udelukkede mindreårige grafer, der tillader afbrudte indlejringer i 3-rum; et bevis på, at hver graf, der ikke er femfarvet, har en komplet graf med seks hjørner som baggrund (firefarvesætningen formodes at give dette resultat, som er et tilfælde af Hadwiger-formodningen ); med Dan Sanders et nyt, forenklet computerbevis for firefarvesætningen; beskrivelse af todelte grafer, der indrømmer en Pfaffian af orientering; og reduktion til næsten fladt tilfælde af Tutts formodning om, at hver kubisk ubrobundet graf, der ikke er tredobbelt, indeholder Petersen-grafen som en mol. (Den resterende "næsten flade sag" blev efterfølgende løst, hvorved man opnåede et fuldstændigt bevis for Tutts formodning; løsningen bruger ikke firefarvesætningen og beviser det desuden i udvidet form).

I 2000 blev trioen støttet af American Institute of Mathematics til at arbejde på den stærke ideelle grafformodning, et åbent problem rejst af Claude Berge i begyndelsen af ​​1960'erne. Seymours elev Maria Chudnovskaya sluttede sig til gruppen i 2001, og i 2002 beviste de fire i fællesskab hypotesen. Seymour fortsatte med at arbejde med Chudnovskaya og opnåede flere resultater på inducerede undergrafer, især (med tre medforfattere) en polynomisk tidsalgoritme til at kontrollere, om en graf er perfekt, og en generel beskrivelse af alle grafer uden kløer . Robertson-Seymour-sætningen  er et resultat opnået i 2004 på grundlag af arbejdet i "graph minors-projektet", som etablerer den fuldstændige kvasi-ordning af sættet af urettede grafer med en minoritetsrelation.

I 2010'erne, i en række værker med Alex Scott og delvist med Chudnovskaya, blev to formodninger af András Gyarfaš bevist, at hver graf med et afgrænset kliktal og et tilstrækkeligt stort kromatisk tal har en induceret cyklus med en ulige længde på mindst fem og har en induceret cyklus af længde på mindst et hvilket som helst specificeret antal.

Noter

1. ↑ Matematisk genealogi  (engelsk) - 1997.

Links

• Paul Seymours hjemmeside på Princeton University

Tematiske steder	Matematisk genealogi zbMATH Åbn
I bibliografiske kataloger BIBSYS: 90602606 GND : 135823757 ISNI : 0000 0001 1614 7793 J9U : 987007434126505171 LCCN : n90695862 NTA : 075231719 NUKAT : n95302988 SUDOC : 091251419 VIAF : 30177296 WorldCat VIAF : 30177296