PROFILPELAJAR.COM

Endre Szemerédi
	Endre Szemerédi
Nascimento	21 de agosto de 1940 (84 anos); Budapeste
Nacionalidade	Húngaro
Alma mater	Universidade Estatal de Moscou
Prêmios	Prêmio Alfréd Rényi (1973), Prêmio George Pólya (1975), Erdős Lectures (2005), Prêmio Schock de Matemática (2008), Prêmio Leroy P. Steele (2008), Prémio Abel (2012)
Orientador(es)(as)	Israel Gelfand
Orientado(a)(s)	Gábor Sárközy
Instituições	Universidade Rutgers
Campo(s)	Ciência da computação

Endre Szemerédi (Budapeste, 21 de agosto de 1940) é um matemático húngaro.

Vida

Nasceu em Budapeste, estudou na Universidade Eötvös Loránd em Budapeste e obteve o doutorado na Universidade Estatal de Moscou, orientado por Israel Gelfand.^[1]

Trabalha nos campos da combinatória e ciência computacional teórica. É desde 1986 professor da Universidade Rutgers. Foi professor visitante na Universidade Stanford (1974), Universidade McGill (1980), Universidade da Carolina do Sul (1981–1983) e Universidade de Chicago (1985–1986).

Trabalho

Endre Szemerédi publicou mais de 200 artigos científicos nas áreas de matemática discreta, ciência da computação teórica, combinatória aritmética e geometria discreta. Ele é mais conhecido por sua prova de 1975 de uma velha conjectura de Paul Erdős e Pál Turán: se uma seqüência de números naturais tem densidade superior positiva então ela contém progressões aritméticas arbitrariamente longas. Isso agora é conhecido como teorema de Szemerédi. Um dos lemas introduzidos em sua prova é agora conhecido como o lema da regularidade de Szemerédi, que se tornou um lema importante em combinatória, sendo usado por exemplo em testes de propriedades para grafos e na teoria dos limites de grafos.

Ele também é conhecido pelo teorema de Szemerédi–Trotter em geometria de incidência e pelo teorema de Hajnal–Szemerédi e pelo problema de Ruzsa–Szemerédi na teoria dos grafos. Miklós Ajtai e Szemerédi provaram o teorema dos cantos, um passo importante para generalizações de dimensão superior do teorema de Szemerédi. Com Ajtai e János Komlós ele provou o limite superior de ct² /log t para o número de Ramsey R (3, t), e construiu uma rede de classificação de profundidade ótima. Com Ajtai, Václav Chvátal e Monroe M. Newborn, Szemerédi provaram o famoso lema de cruzamento, que um grafo com n vértices e m arestas, onde m > 4 n tem pelo menos m³ / 64 n² cruzamentos. Com Paul Erdős, ele provou o teorema de Erdős–Szemerédi sobre o número de somas e produtos em um conjunto finito. Com Wolfgang Paul, Nick Pippenger e William Trotter, ele estabeleceu uma separação entre tempo linear não determinístico e tempo linear determinístico.tempo linear, no espírito do infame problema P versus NP.