Seymour, Paul (matematician)

Paul Seymour (n. 26 iulie 1950, Plymouth , Marea Britanie ) este un matematician britanic și american , profesor la Universitatea Princeton, specialist în teoria grafurilor . El a adus o mare contribuție la studiul matroidelor obișnuite și al matricelor complet unimodulare , teorema celor patru culori , înglobările deconectate , teorema minoră a grafului , ipoteza grafului ideal , conjectura Hadwiger și grafurile fără gheare .

Sloan Scholar (1983), câștigător al Premiului Ostrovsky (2004), Premiul Fulkerson (1979, 1994, 2006, 2009), Premiul Poya (1983, 2004), doctorat onorific de la Universitatea din Waterloo (2008), Universitatea Tehnică Daneză ( 2013). Editor-șef (împreună cu Carsten Thomassen) Jurnalul de teorie a graficelor .

Biografie

A studiat la Plymouth College și apoi la Exeter College, Oxford, obținând o licență în 1971 și un doctorat în 1975.

Între 1974 și 1976 a fost bursier la University College Swansea . Apoi s-a întors la Oxford, unde a lucrat între 1976-1980 ca student la Merton College și între 1978-1979 la Universitatea din Waterloo . Din 1980-1983 a fost profesor adjunct și apoi profesor la Ohio State Research University din Columbus , unde a început cercetările cu Neil Robertson, o colaborare fructuoasă care a continuat mulți ani. Din 1983 până în 1996 a lucrat la Bellcore (Bell Communications Research, acum Telcordia Technologies) din Morristown . A fost, de asemenea, profesor adjunct la Universitatea Rutgers în perioada 1984-1987 și la Universitatea din Waterloo între 1988-1993. În 1996 a devenit profesor la Universitatea Princeton .

Familie

În 1979, s-a căsătorit cu Shelley MacDonald din Ottawa și au doi copii, Amy și Emily. Cuplul s-a separat în 2007. Brother - Linord Seymour - profesor de terapie genetică la Universitatea Oxford .

Contribuții științifice

Combinatoria de la Oxford în anii 1970 a dominat teoria matroidei, prin influența lui Dominic Welsh și Aubrey William Ingleton. O mare parte din lucrările timpurii ale lui Seymour, până în 1980, au fost despre teoria matroidelor și au inclus trei lucrări importante despre matroizi: o disertație de doctorat; o lucrare de caracterizare a minorilor excluși de matroizi reprezentați pe un câmp de trei elemente; și teorema conform căreia toți matroizii obișnuiți sunt compusi din matroizi grafici și cograf adunați într-un mod simplu (rezultat pentru care a fost acordat premiul Poya). Au existat alte câteva lucrări semnificative din această perioadă: o lucrare cu Welsh despre probabilitățile critice de scurgere a legăturilor pe o rețea pătrată; un articol în care este dezvăluită ipoteza acoperirii cu ciclu dublu; un articol despre marginea multicoloră a graficelor cubice, care prefigurează teorema rețelei coincidente a lui Laszlo Lovas; o lucrare care demonstrează că toate graficele fără punte admit 6 fluxuri nicăieri-zero — un pas către confirmarea conjecturii lui Tutt cu 5 fluxuri nicăieri-zero și o lucrare care rezolvă problema cu două căi care a fost motorul multor lucrări viitoare a lui Seymour.

În 1980 s-a mutat la Universitatea de Stat din Ohio, unde a început să lucreze cu Neil Robertson, colaborând la producerea așa-numitului „Graph Minor Project”, o serie de 23 de lucrări publicate în următorii treizeci de ani, cu câteva rezultate semnificative: o teoremă privind structura graficelor minore, că, pentru orice grafic fix, toate graficele care nu îl conțin ca minor pot fi construite din grafice care sunt în esență de gen limitat prin unirea lor pe seturi mici de tăieturi într-o structură de arbore; dovadă a conjecturii lui Wagner că în orice set infinit de grafice, unul dintre ele este minorul celuilalt (și, prin urmare, orice proprietate a graficelor care poate fi caracterizată de minori excluși poate fi caracterizată printr-o listă finită de minori excluși); dovada unei conjecturi similare a lui Nash-Williams că în orice set infinit de grafice, unul dintre ele poate fi încorporat în altul; algoritmi de timp polinomial pentru a verifica dacă un grafic conține un grafic fix ca minor și pentru a rezolva problema k căi disjunse vârfuri pentru toate k fixe.

În jurul anului 1990, Robin Thomas a început să lucreze cu Robertson și Seymour. Ca urmare a colaborării lor în următorii zece ani, au fost pregătite câteva lucrări comune importante: o dovadă a conjecturii Sachs caracterizată prin grafice minore excluse care admit înglobări deconectate în spații 3; o dovadă că fiecare grafic care nu are cinci culori are un grafic complet cu șase vârfuri ca fundal (teorema patru culori ar trebui să dea acest rezultat, care este un caz al conjecturii Hadwiger ); cu Dan Sanders o nouă demonstrație simplificată, pe computer, a teoremei patru culori; descrierea graficelor bipartite care admit un Pfaffian de orientare; și reducerea la un caz aproape plat al conjecturii lui Tutt că fiecare graf cubic nepunct care nu este triplu conține graful Petersen ca minor. („Cazul aproape plat” rămas a fost rezolvat ulterior, obținându-se astfel o demonstrație completă a conjecturii lui Tutt; soluția nu folosește teorema celor patru culori și, în plus, o demonstrează într-o formă extinsă).

În 2000, trio-ul a fost sprijinit de Institutul American de Matematică pentru a lucra la conjectura grafică ideală puternică, o problemă deschisă ridicată de Claude Berge la începutul anilor 1960. Eleva lui Seymour, Maria Chudnovskaya , s-a alăturat grupului în 2001, iar în 2002 cei patru au demonstrat împreună ipoteza. Seymour a continuat să lucreze cu Chudnovskaya și a obținut mai multe rezultate pe subgrafe induse, în special (cu trei coautori) un algoritm de timp polinomial pentru a verifica dacă un grafic este perfect și o descriere generală a tuturor graficelor fără gheare . Teorema Robertson-Seymour  este un rezultat obținut în 2004 pe baza lucrării „proiectului graph minors”, care stabilește cvasi-ordonarea completă a mulțimii de grafuri nedirecționate cu o relație minoritară.

În anii 2010, într-o serie de lucrări cu Alex Scott și parțial cu Chudnovskaya, s-au dovedit două presupuneri ale lui András Gyarfaš că fiecare graf cu un număr de clică mărginit și un număr cromatic suficient de mare are un ciclu indus de lungime impară de cel puțin cinci și are un ciclu indus de lungime cel puțin oricare dintre numărul specificat.

Note

1. ↑ Genealogia matematică  (engleză) - 1997.

Link -uri

• Pagina principală a lui Paul Seymour la Universitatea Princeton

Site-uri tematice	Genealogie matematică zbMATH Deschide
În cataloagele bibliografice BIBSYS: 90602606 GND : 135823757 ISNI : 0000 0001 1614 7793 J9U : 987007434126505171 LCCN : n90695862 NTA : 075231719 NUKAT : n95302988 SUDOC : 091251419 VIAF : 30177296 WorldCat VIAF : 30177296