塞邁雷迪·安德烈

塞邁雷迪·安德烈
Szemerédi Endre
塞邁雷迪·安德烈; Szemerédi Endre
	2010年5月
出生	1940年8月21日（83歲）; 匈牙利布達佩斯
國籍	匈牙利
母校	莫斯科國立大學
獎項	阿貝爾獎 (2012); 波利亞獎 (1975); 肖克獎 (2008); Leroy P. Steele Prize (2008); 倫伊·阿爾弗雷德獎 (1973); 美國國家科學院院士
	科學生涯
研究領域	計算機科學
機構	羅格斯大學
博士導師	伊斯拉埃爾·蓋爾范德
博士生	Jaikumar Radhakrishnan; Ali Shokoufandeh; Ryan Martin; Sachin Lodha; Gabor Sarkozy; Bela Csaba; 趙羿; Ayman Khalfallah; Sarmad Abbasi

匈牙利人名順序為先姓後名。本條目中的譯名遵從此順序。

塞邁雷迪·安德烈（匈牙利語：Szemerédi Endre，1940年8月21日—），匈牙利數學家，他主要的研究領域為組合數學與理論計算機科學。他自從1986年以來一旦擔任美國羅格斯大學的計算機科學教授。

生平[編輯]

塞邁雷迪在離散數學、理論電腦科學、算術組合（英語：Arithmetic combinatorics）、組合幾何方面總共發表了超過200篇學術論文。其中，在1975年，他證明了艾狄胥·帕爾和圖蘭·帕爾的著名猜想：若一個正整數序列有正的上密度，則具有任意長的等差數列。這條定理現在以他為名，稱為塞邁雷迪定理。證明過程當中，他引入了塞邁雷迪正則性引理。引理對於圖的性質檢驗（英語：property testing）和圖極限理論有重要應用。

得名自塞邁雷迪的還有重合幾何的塞邁雷迪－特羅特定理、圖論的豪伊瑙爾－塞邁雷迪定理（英語：Hajnal–Szemerédi theorem）和魯紹－塞邁雷迪問題（英語：Ruzsa–Szemerédi problem）。奧伊陶伊·米克洛什（英語：Miklós Ajtai）和塞邁雷迪證明了拐角定理（英語：corners theorem），是邁向塞邁雷迪定理高維推廣的重要一步。塞邁雷迪與奧伊陶伊和科姆洛什·亞諾什（英語：János Komlós）合作，證明了拉姆齊數R(3,t)的上界ct²/log t，並構造了深度最優的排序網絡（英語：Sorting network）。此外，塞邁雷迪與奧伊陶伊、瓦茨拉夫·赫瓦塔爾（英語：Václav Chvátal）、蒙提·紐邦（英語：Monty Newborn）合作證明了交叉數不等式，即若一幅圖恰有n個頂點和m條邊，且m > 4n，則將其畫在平面上時，必有至少m³ / 64n²個交叉。

1987年他成為匈牙利科學院院士；2010年成為美國國家科學院院士。他也是普林斯頓高等研究院的成員。

2012年3月21日，他獲得挪威科學與文學院授予的阿貝爾獎，「以表彰其在離散數學和理論計算機科學方面的傑出貢獻，以及對堆壘數論和遍歷理論產生的深遠影響。」^[2]^[3]

^ Doctor honoris causa Endre Szemerédi （頁面存檔備份，存於網際網路檔案館）, June 15–16, 2010.
^ Hungarian-American Endre Szemerédi named Abel Prize winner. The Norwegian Academy of Science and Letters. [March 21, 2012]. （原始內容存檔於2012-08-30）.
^ Ramachandran, R. Hungarian mathematician Endre Szemerédi gets 2012 Abel Prize. The Hindu. March 22, 2012 [22 March 2012]. （原始內容存檔於2014-11-29）.