Seymour, Paul (matemaatikko)

Paul Seymour (s. 26. heinäkuuta 1950, Plymouth , UK ) on brittiläinen ja amerikkalainen matemaatikko , Princetonin yliopiston professori, graafiteorian asiantuntija . Hän antoi suuren panoksen säännöllisten matroidien ja täysin unimodulaaristen matriisien , neljän värin lauseen , irrotettujen upotusten , graafisen mollilauseen , ideaalisen graafisen hypoteesin , Hadwiger -oletuksen ja kaavioiden ilman kynsiä tutkimiseen .

Sloan Scholar (1983), Ostrovski-palkinnon (2004), Fulkerson-palkinnon (1979, 1994, 2006, 2009), Poya-palkinnon (1983, 2004) voittaja , Waterloon yliopiston kunniatohtori (2008), Tanskan teknillinen yliopisto ( 2013). Päätoimittaja (Carsten Thomassenin kanssa) Journal of Graph Theory .

Elämäkerta

Hän opiskeli Plymouth Collegessa ja sitten Exeter Collegessa Oxfordissa, ansaitten BA -tutkinnon vuonna 1971 ja tohtorin vuonna 1975.

Vuosina 1974-1976 hän oli college-stipendiaatti University College Swanseassa . Sitten hän palasi Oxfordiin, jossa hän työskenteli vuosina 1976-1980 nuorempana tutkijana Merton Collegessa ja 1978-1979 Waterloon yliopistossa . Vuosina 1980-1983 hän oli dosentti ja sitten professori Ohion osavaltion tutkimusyliopistossa Columbuksessa , missä hän aloitti tutkimuksen Neil Robertsonin kanssa, hedelmällinen yhteistyö, joka jatkui useita vuosia. Vuodesta 1983 vuoteen 1996 hän työskenteli Bellcoressa (Bell Communications Research, nyt Telcordia Technologies) Morristownissa . Hän oli myös dosentti Rutgersin yliopistossa 1984-1987 ja Waterloon yliopistossa 1988-1993. Vuonna 1996 hänestä tuli Princetonin yliopiston professori .

Perhe

Vuonna 1979 hän meni naimisiin Shelley MacDonaldin kanssa Ottawasta , ja heillä on kaksi lasta, Amy ja Emily. Pariskunta erosi vuonna 2007. Veli - Linord Seymour - geeniterapian professori Oxfordin yliopistossa .

Tieteelliset julkaisut

Kombinatoriikka Oxfordissa 1970-luvulla hallitsi matroiditeoriaa Dominic Welshin ja Aubrey William Ingletonin vaikutuksesta. Suuri osa Seymourin varhaisesta työstä, noin vuoteen 1980 asti, koski matroiditeoriaa ja sisälsi kolme tärkeää matroideja koskevaa asiakirjaa: väitöskirja; paperi kolmielementtikentän yli esitettyjen matroidien poissuljettujen alaikäisten luonnehdinnasta; ja lause, jonka mukaan kaikki tavalliset matroidit koostuvat graafisista ja graafisista matroideista, jotka on koottu yksinkertaisella tavalla (josta Poya-palkinto myönnettiin). Tämän ajanjakson jälkeen on ollut useita muita merkittäviä papereita: paperi, jossa on Walesin kriittiset sidosvuodon todennäköisyydet neliöhilassa; artikkeli, jossa esitetään kaksinkertaisen syklin peitteen hypoteesi; artikkeli kuutiograafien reunamoniväristä, joka ennakoi Laszlo Lovasin yhteneväisen hilalauseen; paperi, joka todistaa, että kaikki sillattomat kuvaajat hyväksyvät nollan 6-virtauksen – askel kohti Tuttin ei-nolla-5-virtauksen arvelujen vahvistamista , ja paperi, joka ratkaisee kaksitieongelman, joka oli moottorina suurimmassa osassa Seymourin tulevaa työtä.

Vuonna 1980 hän muutti Ohion osavaltion yliopistoon, jossa hän aloitti työskentelyn Neil Robertsonin kanssa. Hän teki yhteistyötä niin sanotun "Graph Minor Projectin" tuottamiseksi. Se on 23 artikkelin sarja, joka julkaistiin seuraavien 30 vuoden aikana ja jolla on useita merkittäviä tuloksia: lause graafin mollirakenne, että minkä tahansa kiinteän graafin osalta kaikki graafit, jotka eivät sisällä sitä sivuina, voidaan rakentaa graafista, jotka ovat olennaisesti rajoitettua sukua yhdistämällä ne yhteen puurakenteen pienillä leikkauksilla; todiste Wagnerin olettamuksesta, jonka mukaan missä tahansa äärettömässä graafien joukossa yksi niistä on toisen alaikäinen (ja siksi mikä tahansa graafien ominaisuus, jota voidaan luonnehtia poissuljetuilla alaikäisillä, voidaan luonnehtia rajallisella poissuljettujen alaikäisten luettelolla); todiste samanlaisesta Nash-Williams-oletuksesta, jonka mukaan missä tahansa äärettömässä kaaviojoukossa yksi niistä voidaan upottaa toiseen; polynomiaikaalgoritmeja tarkistamaan, sisältääkö graafi kiinteän graafin sivuarvona, ja ratkaisemaan k vertex-disjoint-polun ongelman kaikille kiinteille k:lle.

Noin 1990 Robin Thomas aloitti työskentelyn Robertsonin ja Seymourin kanssa. Seuraavien kymmenen vuoden yhteistyön tuloksena valmistettiin useita tärkeitä yhteisiä papereita: todiste Sachsin arveluista, jotka luonnehtivat poissuljetuista alaikäisten kaavioista, jotka sallivat irrotetut upotukset 3-avaruudessa; todiste siitä, että jokaisella graafilla, joka ei ole viisivärinen, on täydellinen graafi, jossa on kuusi kärkeä taustana (nelivärilauseen oletetaan antavan tämän tuloksen, mikä on Hadwigerin arvelun tapaus ); Dan Sandersin kanssa uusi, yksinkertaistettu tietokonetodiste nelivärilauseesta; kuvaus kaksiosaisista graafista, jotka sallivat orientaation Pfaffian; ja pelkistys lähes tasaiseksi tapaukseksi Tuttin oletuksesta, että jokainen kuutioinen siltaton graafi, joka ei ole kolminkertainen, sisältää Petersenin graafin mollina. (Jäljellä oleva "melkein tasainen tapaus" ratkaistiin myöhemmin, jolloin saatiin täydellinen todiste Tuttin olettamuksesta; ratkaisu ei käytä neljän värin lausetta, ja lisäksi se todistaa sen laajennetussa muodossa).

Vuonna 2000 American Institute of Mathematics tuki kolmikkoa työstämään vahvaa ideaaligrafiikkaarvausta, joka on avoin ongelma, jonka Claude Berge esitti 1960-luvun alussa. Seymourin opiskelija Maria Chudnovskaya liittyi ryhmään vuonna 2001, ja vuonna 2002 he neljä yhdessä todistivat hypoteesin. Seymour jatkoi työskentelyä Chudnovskayan kanssa ja sai useita muita tuloksia indusoiduista aligraafista, erityisesti (kolmen tekijän kanssa) polynomiaikaalgoritmin, jolla tarkistetaan, onko graafi täydellinen, ja yleiskuvauksen kaikista graafisista ilman kynsiä . Robertson-Seymour-lause  on vuonna 2004 saatu tulos "graph minors project" -projektin työn perusteella, joka määrittää suuntaamattomien graafien joukon täysin näennäisen järjestyksen vähemmistösuhteen kanssa.

2010-luvulla Alex Scottin ja osittain Chudnovskajan kanssa tehdyissä töissä osoitettiin kaksi András Gyarfašin oletusta, että jokaisella graafilla, jolla on rajoitettu klikkiluku ja riittävän suuri kromaattinen luku, on indusoitu sykli, jonka pituus on vähintään viisi ja se on indusoitu sykli, jonka pituus on vähintään mikä tahansa määrätty luku.

Muistiinpanot

1. ↑ Matemaattinen sukututkimus  (englanniksi) - 1997.

Linkit

• Paul Seymourin kotisivu Princetonin yliopistossa

Temaattiset sivustot	Matemaattinen sukututkimus zbMATH Avoinna
Bibliografisissa luetteloissa BIBSYS : 90602606 GND : 135823757 ISNI : 0000 0001 1614 7793 J9U : 987007434126505171 LCCN : n90695862 NTA : 075231719 NUKAT : n95302988 SUDOC : 091251419 VIAF : 30177296 WorldCat VIAF : 30177296