Seymour, Paul (matematikus)

A stabil verziót 2022. január 4-én nézték meg . Ellenőrizetlen változtatások vannak a sablonokban vagy a .
Paul Seymour
Születési dátum 1950. július 26. (72 évesen)( 1950-07-26 )
Születési hely Plymouth , Anglia
Ország
Tudományos szféra kombinatorika és gráfelmélet
Munkavégzés helye Princeton egyetem
alma Mater
tudományos tanácsadója Aubrey William Ingleton
Díjak és díjak Osztrovszkij-díj (2003)
Poya-díj (SIAM) (2004)

Paul Seymour (szül. 1950. július 26., Plymouth , Egyesült Királyság ) brit és amerikai matematikus , a Princetoni Egyetem professzora, a gráfelmélet specialistája . Nagy mértékben hozzájárult a szabályos matroidok és a teljesen unimoduláris mátrixok , a négyszín-tétel , a szétválasztott beágyazások , a gráf-moll tétel , az ideális gráf -hipotézis , a Hadwiger-sejtés és a karmok nélküli gráfok tanulmányozásához .

Sloan Scholar (1983), Osztrovszkij-díj (2004), Fulkerson-díj (1979, 1994, 2006, 2009), Poya-díj (1983, 2004), díszdoktora a Waterloo Egyetemen ( 2008), Dán Műszaki Egyetem 2013). Főszerkesztő (Carsten Thomassennel) Journal of Graph Theory .

Életrajz

A Plymouth College-ban, majd az oxfordi Exeter College-ban tanult, 1971-ben BA fokozatot , 1975- ben pedig PhD fokozatot szerzett.

1974 és 1976 között a University College Swansea főiskolai munkatársa volt . Ezután visszatért Oxfordba, ahol 1976 és 1980 között junior ösztöndíjasként dolgozott a Merton College-ban, 1978 és 1979 között pedig a Waterloo Egyetemen . 1980-1983 között adjunktus, majd professzor volt az Ohio Állami Kutatói Egyetemen Columbusban , ahol Neil Robertsonnal kezdett kutatásba, amely gyümölcsöző együttműködés hosszú évekig tartott. 1983-tól 1996-ig a Bellcore-nál (Bell Communications Research, jelenleg Telcordia Technologies) dolgozott Morristownban . 1984 és 1987 között a Rutgers Egyetemen , 1988 és 1993 között pedig a Waterloo Egyetemen volt adjunktus . 1996 - ban a Princetoni Egyetem professzora lett .

Család

1979-ben feleségül vette Shelley MacDonaldot Ottawából , és két gyermekük született, Amy és Emily. A pár 2007-ben vált el. Linord Seymour testvér - az Oxfordi Egyetem génterápia professzora .

Tudományos hozzájárulások

Az 1970-es években Oxfordban a kombinatorika uralta a matroidelméletet Dominic Welsh és Aubrey William Ingleton hatására. Seymour korai munkáinak nagy része, körülbelül 1980-ig, a matroid elmélettel foglalkozott, és három fontos tanulmányt tartalmazott a matroidokról: egy doktori disszertációt; egy dolgozat a matroidok kizárt kiskorúinak jellemzéséről egy háromelemes mezőn keresztül; és az a tétel, hogy minden szabályos matroid egyszerű módon összerakott grafikus és kográf matroidokból áll (ezért a Poya-díjat is odaítélték). Számos más jelentős dokumentum is született azóta: egy walesi írás a kritikus kötésszivárgási valószínűségekről négyzetrácson; egy cikk, amelyben a kettős ciklus lefedésének hipotézisét ismertetik; egy cikk a köbös gráfok éles sokszínűségéről, amely előrevetíti Lovas László egybeeső rácstételét; egy tanulmány, amely bizonyítja, hogy minden híd nélküli gráf nem enged be sehol nulla 6 áramlást – ez egy lépés Tutt sehol nulla 5 áramlású sejtésének megerősítése felé , valamint egy tanulmány, amely megoldja azt a kétutas problémát, amely Seymour jövőbeli munkájának nagy részének motorja volt.

1980-ban az Ohio Állami Egyetemre költözött, ahol Neil Robertsonnal kezdett együtt dolgozni az úgynevezett "Graph Minor Project" elkészítésében, amely egy 23 cikkből álló sorozat a következő harminc évben jelent meg, és számos jelentős eredménnyel: egy tétel a gráf-mollok szerkezete, hogy bármely fix gráf esetében minden olyan gráf, amely nem tartalmazza azt mollként, felállítható olyan gráfokból, amelyek lényegében korlátozott nemzetséghez tartoznak, úgy, hogy azokat egy fastruktúrában kis vágáshalmazokon kapcsoljuk össze; bizonyítéka Wagner sejtésének, miszerint bármely végtelen gráfhalmazban az egyik a másik mollja (és ezért a gráfok bármely tulajdonsága, amely a kizárt kiskorúakkal jellemezhető, a kizárt minorok véges listájával jellemezhető); egy hasonló Nash-Williams sejtés bizonyítéka, miszerint bármely végtelen gráfhalmazban az egyik beágyazható egy másikba; polinomiális idő algoritmusok annak ellenőrzésére, hogy egy gráf tartalmaz-e fix gráfot mellékként, és megoldja a k csúcs-diszjunkt útvonal problémáját az összes rögzített k esetében.

1990 körül Robin Thomas Robertsonnal és Seymourral kezdett együtt dolgozni. Az elkövetkező tíz év során folytatott együttműködésük eredményeként több fontos közös dolgozat is készült: a Sachs-sejtés bizonyítása, amely a kizárt kiskorúak gráfjaival jellemezhető, amelyek 3 térben megengedik a szétkapcsolt beágyazást; annak bizonyítéka, hogy minden nem ötszínű gráfnak van egy teljes gráfja hat csúcsgal, mint háttérrel (a négyszínű tétel állítólag ezt az eredményt adja, ami a Hadwiger-sejtés esete ); Dan Sanders-szel a négyszín-tétel új, egyszerűsített számítógépes bizonyítása; kétrészes gráfok leírása, amelyek Pfaffian orientációt engednek meg; és majdnem lapos esetre redukálva Tutt azon sejtését, hogy minden köbös áthidalatlan gráf, amely nem tripla, tartalmazza a Petersen-gráfot mellékként. (A fennmaradó "majdnem lapos esetet" ezt követően megoldották, így teljes bizonyítást nyerve Tutt sejtésére; a megoldás nem használja a négy szín tételt, sőt kiterjesztett formában bizonyítja azt).

2000-ben a triót az American Institute of Mathematics támogatta, hogy dolgozzanak az erős ideális gráf-sejtésen, amely nyitott probléma, amelyet Claude Berge vetett fel az 1960-as évek elején. Seymour tanítványa, Maria Chudnovskaya 2001-ben csatlakozott a csoporthoz, és 2002-ben ők négyen közösen bebizonyították a hipotézist. Seymour folytatta a munkát Chudnovskaya-val, és számos további eredményt ért el az indukált részgráfokkal kapcsolatban, nevezetesen (három társszerzővel) egy polinomiális idő algoritmust annak ellenőrzésére, hogy egy gráf tökéletes-e, és egy általános leírást az összes karmok nélküli gráfról . A Robertson-Seymour tétel  a „gráf minor projekt” munkája alapján 2004-ben kapott eredmény, amely a kisebbségi relációval rendelkező irányítatlan gráfok halmazának teljesen kvázi rendezését állapítja meg.

A 2010-es években Alex Scott és részben Chudnovskaya munkáiban Gyarfaš András két sejtése bebizonyosodott, miszerint minden korlátos klikkszámú és kellően nagy kromatikus számmal rendelkező gráfnak van páratlan hosszúságú indukált ciklusa legalább öt, és egy indukált ciklus, amelynek hossza legalább a megadott szám tetszőleges számú.

Jegyzetek

  1. ↑ Matematikai genealógia  (angol) - 1997.

Linkek

  Ugrás a Wikidata elemre  Tematikus oldalak