Szemerédi Endre

Szemerédi Endre (Budapest, 1940. augusztus 21. –) a Magyar Szent István-renddel kitüntetett, Abel- és Széchenyi-díjas magyar matematikus, egyetemi tanár, a Magyar Tudományos Akadémia rendes tagja. Nemzetközi tudományos ismertségre tett szert kombinatorikai, számelméleti és algoritmuselméleti kutatásaival, eredményeivel. Legjelentősebb eredményét 1975-ben érte el, amikor Erdős Pál és Turán Pál egyik sejtését bizonyította, miszerint minden pozitív felső sűrűségű sorozat tartalmaz tetszőleges hosszú számtani sorozatot. 1990-től a Rutgers Egyetem számítógép-tudományi tanszékének egyetemi tanára. A Rényi Alfréd Matematikai Kutatóintézet professor emeritusa.

Szemerédi Endre
Életrajzi adatok
Született	1940. augusztus 21. (84 éves) Budapest
Ismeretes mint	magyar matematikus, egyetemi tanár
Nemzetiség	magyar
Iskolái	Eötvös Loránd Tudományegyetem Moszkvai Állami Egyetem
Iskolái
Felsőoktatási intézmény	Eötvös Loránd Tudományegyetem
Pályafutása
Szakterület	Diszkrét matematika
Szakmai kitüntetések
Széchenyi-díj Abel-díj
Hatással voltak rá	Turán Pál, Erdős Pál és Hajnal András
A Wikimédia Commons tartalmaz Szemerédi Endre témájú médiaállományokat.

Szemerédi Endre

Életpályája

Gimnáziumi tanulmányait a mai sashegyi Arany János Általános Iskola és Gimnáziumban végezte. 1960-ban kezdte meg egyetemi tanulmányait az Eötvös Loránd Tudományegyetem Természettudományi Karának matematika–fizika szakán. Itt szerzett középiskolai tanári diplomát 1965-ben. Az egyetemen Erdős Pál és Hajnal András voltak legfontosabb tanárai. A diploma megszerzése után az MTA Rényi Alfréd Matematikai Kutatóintézet (2019-től Rényi Alfréd Matematikai Kutatóintézet) tudományos munkatársaként kapott állást. Emellett 1967 és 1970 között levelező aspiráns volt Moszkvában Iszrail Mojszejevics Gelfandnál. (Ez egy tévedés eredménye volt; Szemerédi valójában Alexander Oszipovics Gelfond tanítványa szeretett volna lenni.)^[1] Hazatérése után tudományos főmunkatársként, később tudományos tanácsadóként dolgozott, majd kutatóprofesszori megbízást kapott. Az 1980-as évektől különböző amerikai egyetemeken volt vendégkutató, vendégprofesszor: Columbia Egyetem, Rutgers Egyetem. 1990-ben utóbbi intézmény számítógép-tudományi tanszékén kapott egyetemi tanári megbízást.

1970-ben védte meg Moszkvában a matematikai tudomány kandidátusi, később Budapesten akadémiai doktori értekezését. Az MTA Matematikai Bizottságának lett tagja. 1982-ben megválasztották a Magyar Tudományos Akadémia levelező, 1987-ben pedig rendes tagjává. 2010-ben a National Academy of Sciences (Amerikai Nemzeti Akadémia) hazai tagjává választották. Akadémiai tisztségei mellett a Bolyai János Matematikai Társulat tagja, valamint az Acta Mathematica, a Studia Mathematicarum, a Combinatorica, illetve a Discrete Mathematics szerkesztőbizottságába is bekerült.

Munkássága

• Nevezetes, nagy port felvert eredménye Erdős és Turán sejtésének bizonyítása: minden pozitív felső sűrűségű sorozat tartalmaz tetszőleges hosszú számtani sorozatot. Ehhez fogalmazta meg és igazolta a regularitási lemmát, ami fontos eszközzé vált a nagy gráfok kutatásában.
• Erdős sejtését igazolva bebizonyította, hogy egy n-tagú számtani sorozatban legfeljebb ${\displaystyle o(n)}$ négyzetszám lehet.
• A. D. Korsunov és Pósa Lajos eredményét megjavítva, Komlós Jánossal igazolja, hogy ha egy G véletlen gráf n szögponttal és

${\displaystyle {\frac {1}{2}}n\log n+{\frac {1}{2}}n\log \log n+cn}$

éllel, ahol c rögzített valós szám, akkor annak valószínűsége, hogy G tartalmaz Hamilton-kört, tart a következő értékhez:

${\displaystyle e^{-e^{-2c}}.}$

• Hajnal Andrással bebizonyította Erdős sejtését: ha egy véges gráfban minden pont foka kisebb k-nál, akkor a gráf egyenletesen kiszínezhető k színnel, azaz úgy, hogy a színosztályok mérete legfeljebb 1-gyel tér el egymástól.
• W. T. Trotterrel igazolta Erdős Pál egy sejtését, eszerint m pont és n egyenes között a síkban legfeljebb ${\displaystyle O(m^{2/3}n^{2/3}+m+n)}$ illeszkedés lehet.
• Ruzsa Z. Imrével igazolta azt a tényt, hogy ha ${\displaystyle f(n)}$ jelöli az n ponton kiválasztható 3 elemű részhalmazok maximális számát, amire nincs hat pont, amely 3 kiválasztott halmazt tartalmaz, akkor

${\displaystyle n^{2-\varepsilon }<f(n)=o(n^{2}).}$

• Ajtai Miklóssal és Komlós Jánossal bebizonyította, hogy van olyan Sidon-sorozat, amelynek n-ig legalább ${\displaystyle c(n\log n)^{1/3}}$ eleme van alkalmas c>0-val.
• Ajtai Miklóssal és Komlós Jánossal igazolta a ${\displaystyle R_{2}(3,n)=O(n^{2}/\log n)}$ Ramsey-számokra vonatkozó becslést.

Díjai, elismerései

• Rényi-díj (1973)
• Pólya-díj (1975)
• MTA Matematikai Díj (1978)
• Akadémiai Díj (1979)
• Leroy P. Steele-díj (2008)
• Rolf Schock-díj (2008)
• Széchenyi-díj (2012)
• Abel-díj (2012)
• Prima díj (2012)
• A Magyar Érdemrend nagykeresztje (2013)^[2]
• Magyar Szent István-rend (2020)

Főbb publikációi

• On Sets of Integers Containing no Four Elements in Arithmetic Progression (1969)
• Proof of a Conjecture of P. Erdos, Combinatorial Theory and its Applications, II (Hajnal Andrással, 1969)
• Hamilton Cycles in Random Graphs, Infinite and Finite Sets (Komlós Jánossal, 1973)
• On Sets of Integers Containing no k Elements in Arithmetic Progression (1975)
• Triple Systems with no Six Points Carrying Three Triangles (Ruzsa Z. Imrével, 1978)
• A Note on Ramsey Numbers (társszerző, 1980)
• A Dense Infinite Sidon Sequence (társszerző, 1981)
• A Lower Bound for Heilbronn’s Problem (társszerző, 1982)
• Extremal Problems in Discrete Geometry (társszerző, 1983)
• Undirected Connectivity in O(log^1.5 n) Space (társszerző, 1992)
• Blow-up Lemma (társszerző, 1997)
• Proof of a Conjecture of Bollobas and Eldridge for Graphs of Maximum Degree Three (társszerző, 2003)