Paul Seymour (matematyk)

Paweł Seymour FRS
Urodzić się	( 1950-07-26 ) 26 lipca 1950 Plymouth , Devon, Anglia
Narodowość	brytyjski
Alma Mater	Uniwersytet Oksfordzki (licencjat, doktorat)
Nagrody	Sloan Fellowship (1983) Nagroda Ostrowskiego (2003) Nagroda George'a Pólyi (1983, 2004) Nagroda Fulkersona (1979, 1994, 2006, 2009)
Kariera naukowa
Instytucje	Princeton University Bellcore University of Waterloo Rutgers University Ohio State University
Doradca doktorski	Aubreya Williama Ingletona
Doktoranci	Maria Chudnovsky Sang-il Oum

Paul D. Seymour FRS (urodzony 26 lipca 1950) to brytyjski matematyk znany ze swojej pracy w matematyce dyskretnej , zwłaszcza teorii grafów . On (wraz z innymi) był odpowiedzialny za ważny postęp w regularnych matroidach i całkowicie jednomodułowych macierzach , twierdzenie o czterech kolorach , bezpołączeniowe osadzenie , drugorzędne grafy i strukturę , idealne przypuszczenie grafów , przypuszczenie Hadwigera , grafy bez pazurów , χ-ograniczenie i hipoteza Erdősa-Hajnala . Wiele z jego ostatnich artykułów jest dostępnych na jego stronie internetowej.

Seymour jest obecnie profesorem matematyki Alberta Baldwina Doda na Uniwersytecie Princeton . W 1983 otrzymał Sloan Fellowship , w 2004 Nagrodę Ostrowskiego ; i (czasami z innymi) zdobył Nagrodę Fulkersona w 1979, 1994, 2006 i 2009 oraz Nagrodę Pólya w 1983 i 2004. Otrzymał tytuł doktora honoris causa Uniwersytetu Waterloo w 2008 r., jeden z Politechniki Duńskiej w 2013 r. i jeden z École normale supérieure de Lyon w 2022 r. Był zaproszonym prelegentem na Międzynarodowym Kongresie Matematyków w 1986 r . oraz mówcą plenarnym na Międzynarodowym Kongresie Matematyków w 1994 r . Został członkiem Towarzystwa Królewskiego w 2022 roku.

Wczesne życie

Seymour urodził się w Plymouth w hrabstwie Devon w Anglii. Był studentem dziennym w Plymouth College , a następnie studiował w Exeter College w Oksfordzie , uzyskując tytuł licencjata w 1971 r. I D.Phil w 1975 r.

Kariera

Od 1974 do 1976 był pracownikiem naukowym kolegium w University College of Swansea , a następnie wrócił do Oksfordu na 1976-1980 jako młodszy pracownik naukowy w Merton College w Oksfordzie , z roku 1978-79 na Uniwersytecie Waterloo . W latach 1980-1983 został współpracownikiem, a następnie profesorem zwyczajnym na Uniwersytecie Stanowym Ohio w Columbus w stanie Ohio , gdzie rozpoczął badania z Neilem Robertsonem , owocną współpracę, która trwała przez wiele lat. Od 1983 do 1996 pracował w Bellcore (Bell Communications Research), Morristown, New Jersey (obecnie Telcordia Technologies ). Był także adiunktem na Rutgers University od 1984 do 1987 i na University of Waterloo od 1988 do 1993. Został profesorem na Uniwersytecie Princeton w 1996. Jest redaktorem naczelnym (wspólnie z Carstenem Thomassenem ) w Journal of Graph Theory i redaktor Combinatorica i Journal of Combinatorial Theory, Series B.

Paul Seymour w 2007 roku (zdjęcie z MFO)

Życie osobiste

Ożenił się z Shelley MacDonald z Ottawy w 1979 roku i mają dwoje dzieci, Amy i Emily. Para rozstała się polubownie w 2007 roku. Jego brat Leonard W. Seymour jest profesorem terapii genowej na Uniwersytecie Oksfordzkim .

Główne składki

Kombinatoryka w Oksfordzie w latach 70. była zdominowana przez teorię matroidów , pod wpływem Dominica Welsha i Aubreya Williama Ingletona . Wiele wczesnych prac Seymoura, do około 1980 roku, dotyczyło teorii matroidów i obejmowało trzy ważne wyniki matroidów: jego D.Phil. praca magisterska o matroidach z właściwością max-flow min-cut (za którą otrzymał swoją pierwszą nagrodę Fulkersona); charakterystyka wykluczonych nieletnich matroidów reprezentowanych na trójelementowym polu; i twierdzenie, że wszystkie regularne matroidy składa się z matroidów graficznych i kgraficznych złożonych w prosty sposób (który zdobył jego pierwszą nagrodę Pólya). Było kilka innych znaczących artykułów z tego okresu: artykuł z Welshem na temat krytycznych prawdopodobieństw perkolacji wiązań na siatce kwadratowej; artykuł na temat wielokolorowości krawędzi grafów sześciennych, który zapowiada twierdzenie László Lovásza o dopasowywaniu sieci ; artykuł dowodzący, że wszystkie grafy bez mostków dopuszczają nigdzie-zerowe 6-przepływy, krok w kierunku nigdzie-zerowej hipotezy Tutte'a o 5-przepływach ; oraz artykuł rozwiązujący problem dwóch ścieżek (wprowadzający również podwójną okładkę cyklu przypuszczenie), które było motorem większości przyszłych prac Seymoura.

W 1980 roku przeniósł się do Ohio State University i rozpoczął pracę z Neilem Robertsonem. Doprowadziło to ostatecznie do najważniejszego osiągnięcia Seymoura, tak zwanego „Projektu Graph Minors”, serii 23 artykułów (wspólnie z Robertsonem), opublikowanych w ciągu następnych trzydziestu lat, z kilkoma znaczącymi wynikami: twierdzenie o strukturze grafów minors , że dla dowolny ustalony graf, wszystkie grafy, które nie zawierają go jako drugorzędnego, można zbudować z grafów, które są zasadniczo ograniczonego rodzaju, składając je razem w małych zestawach wycinków w strukturze drzewa; dowód hipotezy Wagnera że w dowolnym nieskończonym zbiorze grafów jeden z nich jest drugorzędny drugiego (a co za tym idzie, że każda właściwość grafów, która może być scharakteryzowana przez wykluczone drugorzędne, może być scharakteryzowana przez skończoną listę wykluczonych drugorzędnych); dowód podobnego przypuszczenia Nasha-Williamsa, że ​​w dowolnym nieskończonym zbiorze grafów jeden z nich może być zanurzony w innym; oraz algorytmy czasu wielomianowego do sprawdzania, czy wykres zawiera ustalony wykres jako drugorzędny, oraz do rozwiązania problemu rozłącznych ścieżek k wierzchołków dla wszystkich ustalonych k.

Około 1990 roku Robin Thomas rozpoczął współpracę z Robertsonem i Seymourem. Ich współpraca zaowocowała kilkoma ważnymi wspólnymi artykułami w ciągu następnych dziesięciu lat: dowodem hipotezy Sachsa , charakteryzującej wykluczonych nieletnich grafy, które dopuszczają osadzenie bez powiązań w 3-przestrzeni; dowód, że każdy graf, który nie jest pięciokolorowy, ma pełny graf sześciu wierzchołków jako drugorzędny (zakłada się, że twierdzenie o czterech kolorach daje ten wynik, co jest przypadkiem hipotezy Hadwigera ) ; z Danem Sandersem , nowy, uproszczony dowód komputerowy twierdzenie o czterech kolorach ; oraz opis grafów dwudzielnych, które dopuszczają orientacje Pfaffa . W tym samym okresie Seymour i Thomas opublikowali również kilka znaczących wyników: (wraz z Nogą Alonem ) twierdzenie o separatorze dla grafów z wykluczoną drugorzędną, rozszerzające twierdzenie o planarnym separatorze Richarda Liptona i Roberta Tarjana ; artykuł charakteryzujący szerokość drzew pod względem jeżyn ; oraz algorytm czasu wielomianowego do obliczania szerokości gałęzi grafów planarnych.

W 2000 roku Robertson, Seymour i Thomas otrzymali wsparcie Amerykańskiego Instytutu Matematyki w pracy nad hipotezą silnego doskonałego wykresu , słynnym pytaniem otwartym, które zostało postawione przez Claude'a Berge'a na początku lat sześćdziesiątych. Uczennica Seymoura, Maria Chudnovsky, dołączyła do nich w 2001 roku, aw 2002 roku cała czwórka wspólnie potwierdziła przypuszczenie. Seymour kontynuował pracę z Chudnovskim i uzyskał kilka innych wyników dotyczących indukowanych podgrafów, w szczególności (z Cornuéjolsem , Liu i Vuškovićem ) algorytm czasu wielomianowego do sprawdzania, czy graf jest doskonały, oraz ogólny opis wszystkich grafów bez pazurów. Inne ważne wyniki z tego okresu obejmują: (z uczniem Seymoura, Sang-ilem Oumem ) wykonalne algorytmy o stałych parametrach do przybliżania szerokości kliki grafów (w granicach wykładniczych) i szerokości gałęzi matroidów (w granicach liniowych); i (z Czudnowskim) dowód, że pierwiastki wielomianu niezależności każdego wykresu bez pazurów są rzeczywiste.

W 2010 roku Seymour pracował głównie nad ograniczonością χ i hipotezą Erdősa-Hajnala . W serii artykułów z Alexem Scottem i częściowo z Chudnovskim udowodnili dwa przypuszczenia Andrása Gyárfása , że każdy graf z ograniczoną liczbą klik i wystarczająco dużą liczbą chromatyczną ma cykl indukowany o nieparzystej długości co najmniej pięć i ma cykl indukowany o długości co najmniej dowolnej określonej liczby. Seria zakończyła się artykułem Scotta i Seymoura, w którym udowodniono, że dla każdego ustalonego k każdy wykres z wystarczająco dużą liczbą chromatyczną zawiera albo duży pełny podgraf, albo indukowane cykle o wszystkich długościach modulo k, co prowadzi do rozwiązania dwóch przypuszczeń Gila Kalai i Roy Meshulam łączący liczbę chromatyczną grafu z homologią jego kompleksu niezależności . Istniał również algorytm czasu wielomianowego (z Chudnovskim, Scottem i Chudnovskim oraz uczennicą Seymoura, Sophie Spirkl), aby sprawdzić, czy wykres zawiera cykl indukowany o długości większej niż trzy i nieparzysty. Ostatnio ta czwórka wspólnie rozwiązała przypadek 5 cykli hipotezy Erdősa-Hajnala, która mówi, że każdy wykres bez indukowanej kopii 5 cykli zawiera niezależny zbiór lub klikę o wielkości wielomianu.

Zobacz też

• Twierdzenie Robertsona-Seymoura
• Twierdzenie o silnym grafie doskonałym

Linki zewnętrzne

• Strona domowa Paula Seymoura na Uniwersytecie Princeton
• Paul Seymour w Mathematics Genealogy Project