エンドレ・セメレディ（Endre Szemerédi、1940年8月21日 - ）は、ハンガリー生まれのアメリカ合衆国の数学者・計算機科学者であり、組み合わせ論と理論計算機科学の分野で活動している。1986年からラトガース大学で計算機科学のニュージャージー州教授を務めている。ハンガリー科学アカデミーのの名誉教授でもある。
セメレディは、2012年のアーベル賞を含む数学と科学における多数の賞を受賞している。組み合わせ論と計算機科学で多数の発見をしており、その中には、、、、が含まれる。
初期 セメレディはブダペストに生まれた。両親が医者になることを望んだため、セメレディは医科大学に入学するが、6か月後退学する(インタビューでBy Gabor Stockert、「そのような責任を負いながら働くことは私はきっと出来ませんでした。」と説明した)http://www.heidelberg-laureate-forum.org/blog/laureate/endre-szemeredi/Sunita Chand; Ramesh Chandra Parida . Science Reporter, February 2013, p. 17。セメレディはエトヴェシュ・ロラーンド大学で学び、モスクワ大学から博士号を得た。指導教官はイズライル・ゲルファント (Gelfand)だった。これは誤字に由来するというのもセメレディは本来 (Gelfond)と研究したかったからである。
学問上の経歴 セメレディは1986年からラトガース大学で計算機科学のニュージャージー州教授を務めている。1974年スタンフォード大学の、1980年マギル大学の、1981年から1983年までサウスカロライナ大学の、そして1985年から1986年までシカゴ大学の訪問研究者の立場にあった。
業績 セメレディは離散数学、理論計算機科学、数論的組み合わせ論、離散幾何学の分野で200を超える科学論文を発表した。ポール・エルデシュとトゥラーン・パールによる古い予想の1975年からの証明によって、セメレディはよく知られている。その予想とは、もし自然数の列が正のを持てば、それは任意の長さの等差数列を含むだろう、というものである。これは現在として知られている。証明の中で導入された補題の一つはとして知られている。それは組み合わせ論における重要な補題となり、例えばグラフに対するやの理論で使用されている。
セメレディはまたにおけるや、グラフ理論におけるとにより知られている。とセメレディは、を証明し、の高次元一般化への重要なステップとなった。 アイタイとと共同で、セメレディはラムゼー数R(3,t)に対するct2/log t上限を証明し、最適深さのソーティングネットワークを構築した。アイタイと、と共同で、セメレディは有名なクロッシング補題を証明した。その内容は、を満たすn頂点とm辺を持つグラフは少なくともを持つ、というものである。ポール・エルデシュと共同で、セメレディは有限集合における和と積の数に関するを証明した。ウォルフガング・ポール(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)Major US Maths Prize Given to HAS Full Member, Hungarian Academy of Sciences, January 9, 2008. The (数学と計算機科学への多くの基本的な貢献に対して) (2012) The アーベル賞 (離散数学と理論計算機科学への基本的な貢献に対して) (2012)
セメレディは、ハンガリー科学アカデミーの通信会員 (1982)、会員 (1987)となり、そして米国科学アカデミーの会員 (2010)となった。プリンストン高等研究所のメンバーでもあり、ブダペストのの終身研究フェローでもある。1987年から1988年の間は、カリフォルニア工科大学のFairchild Distinguished Scholarだった。セメレディはプラハのプラハ・カレル大学の名誉博士である。また、コロラド大学でのForty-Seventh Annual DeLong Lecture SeriesDeLong Lecture Series. Math.colorado.edu. Retrieved on March 22, 2012.の講演者だった。セメレディはモントリオール大学のCRM(Centre de recherches mathématiques)のAisenstadt Chairも務めているAisenstadt Chair Recipients. Crm.umontreal.ca. Retrieved on March 22, 2012.。2008年、バークレー (カリフォルニア州)ののEisenbud Professorだった。
2012年、セメレディは「離散数学と理論計算機科学への貢献に対して、そして加法的整数論（英語版）とエルゴード理論への貢献の深く永久的な影響への表彰で」、アーベル賞を受賞した。アーベル賞の表彰ではまた、組み合わせ論を数学の舞台の中央に持ってきたのはセメレディの功績だとし、数学への問題解決のアプローチを強調したジョージ・ポリアのようなハンガリーの数学者の伝統におけるセメレディの立場を指摘した。セメレディは発表に対し、「私自身の個人的な業績ではなく、数学のこの分野とハンガリーの数学者に対する表彰(このことはセメレディに最高の喜びだった)である」と述べて反応した。
会議
2010年8月2日から7日、とは、エンドレ・セメレディの生誕70歳記念会議を組織したSzemerédi is 70. Renyi.hu. Retrieved on March 22, 2012.。 会議の前に、ボヤイ数学会研究シリーズの一冊で、とにより編纂された全集である『An Irregular Mind』が、セメレディの業績を祝うために70歳の誕生日に出版されたAn Irregular Mind. Springer. Retrieved on March 22, 2012.An Irregular Mind. Amazon. Retrieved on March 22, 2012.。セメレディの業績を祝うための別の会議は、Third Abel Conference: A Mathematical Celebration of Endre SzemerédiであるThird Abel Conference: A Mathematical Celebration of Endre Szemerédi。
私生活 セメレディは既婚者であり、5人の子供がいる。
出典
外部リンク
Personal Homepage at the Alfréd Rényi Institute of Mathematics 6,000,000 and Abel Prize - Numberphile Interview by Gabor Stockert (translated from the Hungarian into English by Zsuzsanna Dancso)