エンドレ・セメレディ

エンドレ・セメレディ（Endre Szemerédi、1940年8月21日 - ）は、ハンガリー生まれのアメリカ合衆国の数学者・計算機科学者であり^[1]、組み合わせ論と理論計算機科学の分野で活動している。1986年からラトガース大学で計算機科学のニュージャージー州教授を務めている。ハンガリー科学アカデミーのアルフレード・レーニ数学研究所（英語版）の名誉教授でもある。

エンドレ・セメレディ
エンドレ・セメレディ
生誕	(1940-08-21) 1940年8月21日（84歳） ブダペスト, ハンガリー王国
国籍	ハンガリー, アメリカ合衆国
研究分野	組み合わせ論 計算機科学 数学 理論計算機科学
研究機関	ラトガース大学
出身校	モスクワ大学
博士課程 指導教員	イズライル・ゲルファント
博士課程 指導学生	ジャイクマール・ラダクリシュナン（英語版） ガーボル・N・シャルケジ（英語版）
主な受賞歴	アーベル賞 (2012) セーチェーニ賞（英語版） (2012) ショック賞 (2008) スティール賞 (2008) ポリヤ賞 (応用数理学会) (1975) アルフレード・レーニ賞（英語版） (1973)
プロジェクト:人物伝

セメレディは、2012年のアーベル賞を含む数学と科学における多数の賞を受賞している。組み合わせ論と計算機科学で多数の発見をしており、その中にはセメレディの定理（英語版）、セメレディの正則性の補題（英語版）、エルデシュ・セメレディの定理（英語版）、ハイナル・セメレディの定理（英語版）、セメレディ・トロッターの定理（英語版）が含まれる。

初期

セメレディはブダペストに生まれた。両親が医者になることを望んだため、セメレディは医科大学に入学するが、6か月後退学する(インタビューで^[2]、「そのような責任を負いながら働くことは私はきっと出来ませんでした。」と説明した)^[3][4][5]。セメレディはブダペストのエトヴェシュ・ロラーンド大学で学び、モスクワ大学から博士号を得た。指導教官はイズライル・ゲルファント (Gelfand)だった^[6]。これは誤字に由来する、というのもセメレディは本来アレキサンダー・ゲルフォント（英語版） (Gelfond)と研究したかったからである^[3]。

学問上の経歴

セメレディは1986年からラトガース大学で計算機科学のニュージャージー州教授を務めている。1974年スタンフォード大学の、1980年マギル大学の、1981年から1983年までサウスカロライナ大学の、そして1985年から1986年までシカゴ大学の訪問研究者の立場にあった。

業績

セメレディは離散数学、理論計算機科学、数論的組み合わせ論、離散幾何学の分野で200を超える科学論文を発表した。ポール・エルデシュとトゥラーン・パールによる古い予想の1975年からの証明によって、セメレディはよく知られている。その予想とは、もし自然数の列が正の上限密度（英語版）を持てば、それは任意の長さの等差数列を含むだろう、というものである。これは現在セメレディの定理（英語版）として知られている。証明の中で導入された補題の一つはセメレディの正則性の補題（英語版）として知られている。それは組み合わせ論における重要な補題となり、例えばグラフに対する特性試験（英語版）やグラフォン（英語版）の理論で使用されている。

セメレディはまた接続幾何学（英語版）におけるセメレディ・トロッターの定理（英語版）や、グラフ理論におけるハイナル・セメレディの定理（英語版）とルザ・セメレディ問題（英語版）により知られている。ミクローシュ・アイタイ（英語版）とセメレディは、コーナーズ定理（英語版）を証明し、セメレディの定理（英語版）の高次元一般化への重要なステップとなった。 アイタイとヤノーシュ・コムロス（英語版）と共同で、セメレディはラムゼー数R(3,t)に対するct²/log t上限を証明し、最適深さのソーティングネットワークを構築した。アイタイとヴァーツラフ・フバータル（英語版）、モンティー・ニューボーン（英語版）と共同で、セメレディは有名なクロッシング補題を証明した。その内容は、m > 4nを満たすn頂点とm辺を持つグラフは少なくともm³ / 64n²クロッシング（英語版）を持つ、というものである。ポール・エルデシュと共同で、セメレディは有限集合における和と積の数に関するエルデシュ・セメレディの定理（英語版）を証明した。ウォルフガング・ポール(Wolfgang Paul)とニック・ピッペンガー（英語版）、ウィリアム・トロッター（英語版）と共同で、セメレディは非決定性線形時間と決定性線形時間の分離を、悪名高いP≠NP予想の精神で確立した。

賞と名誉

セメレディは数学と計算機科学への貢献により数多くの賞と名誉を得た。その内のいくつかは以下の通りである。

• Grünwald Prize (1967)
• Grünwald Prize (1968)
• アルフレード・レーニ賞（英語版） (1973)
• ポリヤ賞 (応用数理学会) (SIAM), (1975)
• Prize of the Hungarian Academy of Sciences (1979)
• State of New Jersey Professorship (1986)
• スティール賞 (研究に対する独創的な貢献に対して) (AMS), (2008)
• ショック賞 (整数の部分集合における等差数列に関する1975年からの深く先駆的な業績に対して) (2008)^[7]
• The セーチェーニ賞（英語版） (数学と計算機科学への多くの基本的な貢献に対して) (2012)
• The アーベル賞 (離散数学と理論計算機科学への基本的な貢献に対して) (2012)

セメレディは、ハンガリー科学アカデミーの通信会員 (1982)、会員 (1987)となり、そして米国科学アカデミーの会員 (2010)となった。プリンストン高等研究所のメンバーでもあり、ブダペストのアルフレード・レーニ数学研究所（英語版）の終身研究フェローでもある。1987年から1988年の間は、カリフォルニア工科大学のFairchild Distinguished Scholarだった。セメレディはプラハのプラハ・カレル大学の名誉博士である^[8]。また、コロラド大学でのForty-Seventh Annual DeLong Lecture Series^[9]の講演者だった。セメレディはモントリオール大学のCRM(Centre de recherches mathématiques)のAisenstadt Chairも務めている^[10]。2008年、バークレー (カリフォルニア州)のMSRI（英語版）のEisenbud Professorだった。

2012年、セメレディは「離散数学と理論計算機科学への貢献に対して、そして加法的整数論（英語版）とエルゴード理論への貢献の深く永久的な影響への表彰で」、アーベル賞を受賞した^[11]。アーベル賞の表彰ではまた、組み合わせ論を数学の舞台の中央に持ってきたのはセメレディの功績だとし、数学への問題解決のアプローチを強調したジョージ・ポリアのようなハンガリーの数学者の伝統におけるセメレディの立場を指摘した^[12]。セメレディは発表に対し、「私自身の個人的な業績ではなく、数学のこの分野とハンガリーの数学者に対する表彰(このことはセメレディに最高の喜びだった)である」と述べて反応した^[13]。

会議

2010年8月2日から7日、アルフレード・レーニ数学研究所（英語版）とヤノーシュ・ボヤイ数学会（英語版）は、エンドレ・セメレディの生誕70歳記念会議を組織した^[14]。 会議の前に、ボヤイ数学会研究シリーズの一冊で、イムレ・バーラーニ（英語版）とヨージェフ・ソリモシ（英語版）により編纂された全集である『An Irregular Mind』が、セメレディの業績を祝うために70歳の誕生日に出版された^[15][16]。セメレディの業績を祝うための別の会議は、Third Abel Conference: A Mathematical Celebration of Endre Szemerédiである^[17]。

私生活

セメレディは既婚者であり、5人の子供がいる^[9]。