エンドレ・セメレディ

エンドレ・セメレディ（"Endre Szemerédi"、1940年8月21日 - ）は、ハンガリー生まれのアメリカ合衆国の数学者・計算機科学者であり、組み合わせ論と理論計算機科学の分野で活動している。1986年からラトガース大学で計算機科学のニュージャージー州教授を務めている。ハンガリー科学アカデミーのの名誉教授でもある。
セメレディは、2012年のアーベル賞を含む数学と科学における多数の賞を受賞している。組み合わせ論と計算機科学で多数の発見をしており、その中には、、、、が含まれる。
初期.
セメレディはブダペストに生まれた。両親が医者になることを望んだため、セメレディは医科大学に入学するが、6か月後退学する(インタビューで、「そのような責任を負いながら働くことは私はきっと出来ませんでした。」と説明した)。セメレディはブダペストのエトヴェシュ・ロラーンド大学で学び、モスクワ大学から博士号を得た。指導教官はイズライル・ゲルファント (Gelfand)だった。これは誤字に由来する、というのもセメレディは本来 (Gelfond)と研究したかったからである。
学問上の経歴.
セメレディは1986年からラトガース大学で計算機科学のニュージャージー州教授を務めている。1974年スタンフォード大学の、1980年マギル大学の、1981年から1983年までサウスカロライナ大学の、そして1985年から1986年までシカゴ大学の訪問研究者の立場にあった。
業績.
セメレディは離散数学、理論計算機科学、数論的組み合わせ論、離散幾何学の分野で200を超える科学論文を発表した。ポール・エルデシュとトゥラーン・パールによる古い予想の1975年からの証明によって、セメレディはよく知られている。その予想とは、もし自然数の列が正のを持てば、それは任意の長さの等差数列を含むだろう、というものである。これは現在として知られている。証明の中で導入された補題の一つはとして知られている。それは組み合わせ論における重要な補題となり、例えばグラフに対するやの理論で使用されている。
セメレディはまたにおけるや、グラフ理論におけるとにより知られている。とセメレディは、を証明し、の高次元一般化への重要なステップとなった。 アイタイとと共同で、セメレディはラムゼー数"R"(3,"t")に対する"ct"2/log "t"上限を証明し、最適深さのソーティングネットワークを構築した。アイタイと、と共同で、セメレディは有名なクロッシング補題を証明した。その内容は、を満たす"n"頂点と"m"辺を持つグラフは少なくともを持つ、というものである。ポール・エルデシュと共同で、セメレディは有限集合における和と積の数に関するを証明した。ウォルフガング・ポール(Wolfgang Paul)と、と共同で、セメレディは非決定性線形時間と決定性線形時間の分離を、悪名高いP≠NP予想の精神で確立した。
賞と名誉.
セメレディは数学と計算機科学への貢献により数多くの賞と名誉を得た。その内のいくつかは以下の通りである。
セメレディは、ハンガリー科学アカデミーの通信会員 (1982)、会員 (1987)となり、そして米国科学アカデミーの会員 (2010)となった。プリンストン高等研究所のメンバーでもあり、ブダペストのの終身研究フェローでもある。1987年から1988年の間は、カリフォルニア工科大学のFairchild Distinguished Scholarだった。セメレディはプラハのプラハ・カレル大学の名誉博士である。また、コロラド大学でのForty-Seventh Annual DeLong Lecture Seriesの講演者だった。セメレディはモントリオール大学のCRM(Centre de recherches mathématiques)のAisenstadt Chairも務めている。2008年、バークレー (カリフォルニア州)ののEisenbud Professorだった。
2012年、セメレディは「離散数学と理論計算機科学への貢献に対して、そして加法的整数論（英語版）とエルゴード理論への貢献の深く永久的な影響への表彰で」、アーベル賞を受賞した。アーベル賞の表彰ではまた、組み合わせ論を数学の舞台の中央に持ってきたのはセメレディの功績だとし、数学への問題解決のアプローチを強調したジョージ・ポリアのようなハンガリーの数学者の伝統におけるセメレディの立場を指摘した。セメレディは発表に対し、「私自身の個人的な業績ではなく、数学のこの分野とハンガリーの数学者に対する表彰(このことはセメレディに最高の喜びだった)である」と述べて反応した。
会議.
2010年8月2日から7日、とは、エンドレ・セメレディの生誕70歳記念会議を組織した。
会議の前に、ボヤイ数学会研究シリーズの一冊で、とにより編纂された全集である『An Irregular Mind』が、セメレディの業績を祝うために70歳の誕生日に出版された。セメレディの業績を祝うための別の会議は、Third Abel Conference: A Mathematical Celebration of Endre Szemerédiである。
私生活.
セメレディは既婚者であり、5人の子供がいる。