Seymour, Paul (matematiker)

Paul Seymour (f. 26 juli 1950, Plymouth , Storbritannien ) är en brittisk och amerikansk matematiker , professor vid Princeton University, specialist på grafteori . Han gjorde ett stort bidrag till studiet av vanliga matroider och helt unimodulära matriser , fyrafärgssatsen , bortkopplade inbäddningar , grafens mindre sats , den ideala grafhypotesen , Hadwiger-förmodan och grafer utan klor .

Sloan Scholar (1983), vinnare av Ostrovsky-priset (2004), Fulkerson-priset (1979, 1994, 2006, 2009), Poya-priset (1983, 2004), hedersdoktor från University of Waterloo (2008), Danish Technical University ( 2013). Chefredaktör (med Carsten Thomassen) Journal of Graph Theory .

Biografi

Han studerade vid Plymouth College och sedan vid Exeter College, Oxford, och tog en BA 1971 och en doktorsexamen 1975.

Mellan 1974 och 1976 var han collegekollega vid University College Swansea . Han återvände sedan till Oxford, där han arbetade från 1976-1980 som juniorstipendiat vid Merton College och från 1978-1979 vid University of Waterloo . Från 1980-1983 var han adjungerad professor och sedan professor vid Ohio State Research University i Columbus , där han började forska med Neil Robertson, ett fruktbart samarbete som fortsatte i många år. Från 1983 till 1996 arbetade han på Bellcore (Bell Communications Research, nu Telcordia Technologies) i Morristown . Han var också adjungerad professor vid Rutgers University 1984-1987 och vid University of Waterloo 1988-1993. 1996 blev han professor vid Princeton University .

Familj

1979 gifte han sig med Shelley MacDonald från Ottawa och de har två barn, Amy och Emily. Paret separerade 2007. Bror - Linord Seymour - professor i genterapi vid Oxford University .

Vetenskapliga bidrag

Kombinatorik vid Oxford på 1970-talet dominerade matroidteorin, genom inflytande från Dominic Welsh och Aubrey William Ingleton. Mycket av Seymours tidiga arbete, fram till omkring 1980, handlade om matroideori och inkluderade tre viktiga artiklar om matroider: en doktorsavhandling; en uppsats om karaktäriseringen av de uteslutna minderåriga av matroider representerade över ett treelementfält; och satsen att alla vanliga matroider är sammansatta av grafiska och kografiska matroider sammansatta på ett enkelt sätt (ett resultat för vilket Poya-priset delades ut). Det har funnits flera andra viktiga artiklar sedan denna period: en artikel med walesiska om sannolikheter för kritiska bindningsläckage på ett kvadratiskt gitter; en artikel i vilken den dubbla cykelomslagshypotesen avslöjas; en artikel om kanten flerfärgade av kubiska grafer, som förebådar Laszlo Lovas sammanfallande gittersats; ett papper som bevisar att alla brolösa grafer medger ingenstans-noll 6-flöden – ett steg mot att bekräfta Tutts ingenstans-noll 5-flödesförmodan , och ett papper som löser det tvåvägsproblem som var motorn i mycket av Seymours framtida arbete.

1980 flyttade han till Ohio State University där han började arbeta med Neil Robertson, och samarbetade för att producera det så kallade "Graph Minor Project", en serie av 23 artiklar publicerade under de kommande trettio åren, med flera betydande resultat: en sats om strukturen för grafiska mindre, att för alla fasta grafer kan alla grafer som inte innehåller den som en moll byggas från grafer som i huvudsak är av begränsat släkte genom att sammanfoga dem på små uppsättningar av snitt i en trädstruktur; bevis på Wagners gissning att i vilken oändlig uppsättning grafer som helst, är den ena av dem en minor av den andra (och därför kan alla egenskaper hos grafer som kan karakteriseras av uteslutna biroller karakteriseras av en ändlig lista över uteslutna biroller); bevis på en liknande Nash-Williams gissning att i vilken oändlig uppsättning grafer som helst kan en av dem bäddas in i en annan; polynomtidsalgoritmer för att kontrollera om en graf innehåller en fast graf som en underordnad, och lösa problemet med k vertex-disjunkta vägar för alla fasta k.

Runt 1990 började Robin Thomas arbeta med Robertson och Seymour. Som ett resultat av deras samarbete under de kommande tio åren utarbetades flera viktiga gemensamma papper: ett bevis på Sachs gissningar som karakteriseras av uteslutna mindreåriga grafer som tillåter frånkopplade inbäddningar i 3-utrymmen; ett bevis på att varje graf som inte är femfärgad har en komplett graf med sex hörn som bakgrund (fyrfärgssatsen är tänkt att ge detta resultat, vilket är ett fall av Hadwiger -förmodan ); med Dan Sanders ett nytt, förenklat datorbevis på fyrfärgssatsen; beskrivning av tvådelade grafer som tillåter en Pfaffian av orientering; och reducering till nästan platt fall av Tutts gissning att varje kubisk oöverbryggad graf som inte är trippel innehåller Petersen-grafen som en moll. (Det återstående "nästan platta fallet" löstes sedan, och fick på så sätt ett fullständigt bevis på Tutts gissning; lösningen använder inte fyrfärgssatsen, och bevisar det dessutom i utökad form).

År 2000 fick trion stöd av American Institute of Mathematics för att arbeta med den starka idealgrafförmodan, ett öppet problem som togs upp av Claude Berge i början av 1960-talet. Seymours student Maria Chudnovskaya gick med i gruppen 2001, och 2002 bevisade de fyra tillsammans hypotesen. Seymour fortsatte att arbeta med Chudnovskaya och fick flera resultat på inducerade subgrafer, särskilt (med tre medförfattare) en polynomtidsalgoritm för att kontrollera om en graf är perfekt, och en allmän beskrivning av alla grafer utan klor . Robertson-Seymour-satsen  är ett resultat som erhölls 2004 på grundval av arbetet i "graph minors-projektet", som fastställer den fullständiga kvasi-ordningen av uppsättningen oriktade grafer med en minoritetsrelation.

På 2010-talet, i en serie arbeten med Alex Scott och delvis med Chudnovskaya, bevisades två gissningar av András Gyarfaš att varje graf med ett begränsat klicktal och ett tillräckligt stort kromatiskt tal har en inducerad cykel med en udda längd på minst fem och har en inducerad cykel av längd åtminstone vilket som helst av det specificerade antalet.

Anteckningar

1. ↑ Mathematical Genealogy  (engelska) - 1997.

Länkar

• Paul Seymours hemsida vid Princeton University

Tematiska platser	Matematisk släktforskning zbMATH Öppna
I bibliografiska 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