Loading article…
ポール・D・シーモアFRS (1950 年生まれ) は、離散数学、特にグラフ理論の研究で知られるイギリスの数学者です。彼は (他の研究者と共に)正則マトロイドと完全ユニモジュラー行列、四色定理、リンクレス埋め込み、グラフマイナーと構造、完全グラフ予想、ハドウィガー予想、クローフリーグラフ、χ-有界性、エルデシュ-ハジナル予想に関する重要な進歩に貢献しました。彼の最近の論文の多くは、彼の Web サイトから入手できます。[ 1 ]
シーモアは現在、プリンストン大学のアルバート・ボールドウィン・ドッド数学教授である。[ 2 ]彼は1983年にスローン・フェローシップ、 2003年にオストロフスキー賞を受賞し、 [ 3 ]また（時には他の研究者と共同で）1979年、1994年、2006年、2009年にフルカーソン賞、 1983年と2004年にポリア賞を受賞している。彼は2008年にウォータールー大学、 2013年にデンマーク工科大学、 2022年にリヨン高等師範学校から名誉博士号を授与された。彼は1986年の国際数学者会議に招待講演者として、また1994年の国際数学者会議に基調講演者として参加した。彼は2022年に王立協会のフェローになった。 [ 4 ]
シーモアは1950年にイングランドのプリマスで生まれた。 [ 5 ]シーモアはプリマス・カレッジの学生であり、[ 6 ]その後オックスフォードのエクセター・カレッジで学び、1971年に 学士号、 1972年に修士号、 1975年に博士号と修士号を取得した。 [ 7 ]彼の博士論文「マトロイド、ハイパーグラフ、および最大フロー最小カット定理」は、オーブリー・ウィリアム・イングルトンの指導を受けた。[ 8 ]
1974年から1976年まで、彼はスウォンジー大学ユニバーシティ・カレッジの研究員を務めた。その後、1976年から1980年までオックスフォード大学マートン・カレッジのジュニア・リサーチ・フェローとしてオックスフォードに戻り、1978年から1979年はウォータールー大学に在籍した。[ 7 ] 1980年から1983年まで、オハイオ州コロンバスのオハイオ州立大学で准教授、その後教授となり、ニール・ロバートソンとの研究を開始した。この実りある共同研究は何年も続いた。1983年から1996年まで、彼はニュージャージー州モリスタウンのベルコア（ベル・コミュニケーションズ・リサーチ）（現在のテルコーディア・テクノロジーズ）の上級科学者であった。彼はまた、1984年から1987年までラトガース大学、1988年から1993年までウォータールー大学で非常勤教授を務めた。1996年にプリンストン大学の教授になった。 [ 7 ]プリンストン大学では、2016年にアルバート・ボールドウィン・ドッド教授職を与えられた。[ 5 ]
彼は、Journal of Graph Theory [ 9 ]の編集長（Carsten Thomassenと共同）であり、 Combinatorica [ 10 ]およびJournal of Combinatorial Theory, Series B [ 11 ]の編集者でもある。
シーモアの弟、レナード・W・シーモアはオックスフォード大学の遺伝子治療学教授である。[ 12 ] 1979年、シーモアは結婚し、2人の子供をもうけた。[ 5 ]
1970年代のオックスフォードにおける組み合わせ論は、ドミニク・ウェルシュとオーブリー・ウィリアム・イングルトンの影響により、マトロイド理論が主流であった。1980年頃までのシーモアの初期の研究の多くはマトロイド理論に関するもので、3つの重要なマトロイドの結果が含まれていた。最大フロー最小カット特性を持つマトロイドに関する博士論文[ pub 1 ]（これにより彼は最初のフルカーソン賞を受賞した）、3要素体上で表現可能なマトロイドの除外マイナーによる特徴付け[ pub 2 ] 、およびすべての正則マトロイドは、単純な方法で組み合わせたグラフィックマトロイドとコグラフィックマトロイド、およびR 10と呼ばれる特別なマトロイドから構成されるという定理[ pub 3 ]（これにより彼は最初のポリア賞を受賞した）。この時期には他にもいくつかの重要な論文があった。正方格子上の結合パーコレーションの臨界確率に関するウェルシュとの共著論文。[ pub 4 ] 3次グラフの辺多彩色に関する論文、[ pub 5 ]ラースロー・ロヴァースのマッチング格子定理を予見する論文、すべてのブリッジレスグラフがどこにもゼロのない6フローを持つことを証明する論文、[ pub 6 ]タットのどこにもゼロのない5フロー予想への一歩、そして2パス問題を解決した論文（サイクル二重被覆予想も導入）、[ pub 7 ]がシーモアのその後の研究の多くを支える原動力となった。
1980年、彼はオハイオ州立大学に移り、ニール・ロバートソンと共同研究を始めた。これが最終的に、シーモアの最も重要な業績である、いわゆる「グラフマイナープロジェクト」につながった。これは、その後30年間にわたって発表された23本の論文（ロバートソンとの共同研究）からなるシリーズで、いくつかの重要な成果がある。グラフマイナー構造定理、任意の固定グラフに対して、それをマイナーとして含まないすべてのグラフは、本質的に有界種数のグラフから、木構造の小さなカットセットでそれらをつなぎ合わせることによって構築できる。[ pub 8 ]ワグナー の予想の証明、任意の無限グラフの集合において、そのうちの1つは別のグラフのマイナーである（したがって、除外されたマイナーによって特徴付けられるグラフの任意の特性は、除外されたマイナーの有限リストによって特徴付けられる）。[ pub 9 ]ナッシュ・ウィリアムズ の同様の予想、すなわち任意の無限グラフ集合において、そのうちの1つが別のグラフに埋め込まれるという予想の証明。[ pub 10 ] グラフが固定グラフをマイナーとして含むかどうかをテストし、すべての固定kに対してk頂点素なパス問題を解くための多項式時間アルゴリズム。[ pub 11 ]
1990 年頃、ロビン・トーマスはロバートソンとシーモアと共同研究を始めた。彼らの共同研究は、その後 10 年間にわたっていくつかの重要な共同論文を生み出した。3次元空間にリンクレス埋め込みを許容するグラフを除外マイナーで特徴付けるサックス予想の証明[ pub 12 ] 5 色付けできないすべてのグラフは、マイナーとして 6 頂点完全グラフを持つことの証明 (この結果を得るには 4 色定理が仮定されており、これはハドウィガー予想の場合である) [ pub 13 ]ダン・サンダース との共同研究による、コンピュータベースの簡略化された新しい4 色定理の証明[ pub 14 ]およびパフィアン方向付けを 許容する二部グラフの説明。[ pub 15 ] 同時期に、シーモアとトーマスはいくつかの重要な成果も発表した。（ノガ・アロンと共同で）除外マイナーを持つグラフの分離定理、[ pub 16 ]リチャード・リプトンとロバート・タージャンの平面分離定理の拡張、イバラによる木幅の特徴付けに関する論文、[ pub 17 ]および平面グラフの枝幅を計算する多項式時間アルゴリズム。[ pub 18 ]
2000年、ロバートソン、シーモア、トーマスは、アメリカ数学協会の支援を受けて、 1960年代初頭にクロード・ベルジュが提起した有名な未解決問題である強力な完全グラフ予想に取り組んだ。2001年にシーモアの学生であるマリア・チュドノフスキーが加わり、2002年に4人は共同でこの予想を証明した。[ pub 19 ]シーモアはチュドノフスキーとの研究を続け、誘導部分グラフに関するいくつかの成果を得た。特に、（コルヌジョルス、リュウ、ヴシュコヴィッチと共同で）グラフが完全かどうかをテストする多項式時間アルゴリズム[ pub 20 ]と、すべてのクローフリーグラフの一般的な記述を得た。[ pub 21 ]この時期のその他の重要な成果には、(Seymour の学生Sang-il Oumと共同で)グラフのクリーク幅(指数関数的限界内) とマトロイドの枝幅 (線形限界内)を近似する固定パラメータ扱いやすいアルゴリズム、 [ pub 22 ]および (Chudnovsky と共同で) クローフリーグラフの独立多項式の根が実数であることの証明[ pub 23 ]などがあります。
2010 年代、Seymour は主にχ-有界性とErdős–Hajnal 予想に取り組んでいました。Alex Scott と共同で、また一部は Chudnovsky と共同で発表した一連の論文で、András Gyárfásの 2 つの予想、すなわち、有界クリーク数と十分に大きな彩色数を持つすべてのグラフには、少なくとも 5 の奇数長の誘導サイクルが存在すること[ pub 24 ]、および、少なくとも任意の指定された数の長さの誘導サイクルが存在すること[ pub 25 ]を証明しました。この一連の研究は、Scott と Seymour による論文で最高潮に達し、固定された任意の k に対して、十分に大きな彩色数を持つすべてのグラフには、大きな完全部分グラフまたは k を法とするすべての長さの誘導サイクルのいずれかが含まれることを証明しました[ pub 26 ]。これは、グラフの彩色数とその独立複体のホモロジーを関連付けるGil Kalaiと Roy Meshulamの 2 つの予想の解決につながります。また、グラフに長さが 3 より大きく奇数の誘導サイクルが含まれているかどうかをテストする多項式時間アルゴリズム (Chudnovsky、Scott、Chudnovsky と Seymour の学生 Sophie Spirkl との共同) も存在した。[ pub 27 ]ごく最近では、この 4 人は共同で、誘導 5 サイクルのコピーを持たないすべてのグラフには独立集合または多項式サイズのクリークが含まれるという Erdős–Hajnal 予想の 5 サイクルの場合を解決した。[ pub 28 ]
