Endre Szemerédi

Origem: Wikipédia, a enciclopédia livre.
Endre Szemerédi
Nascimento 21 de agosto de 1940 (82 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[editar | editar código-fonte]

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[editar | editar código-fonte]

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 ct2 /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 m3 / 64 n2 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.

Ver também[editar | editar código-fonte]

Referências

Ligações externas[editar | editar código-fonte]

O Commons possui uma categoria com imagens e outros ficheiros sobre Endre Szemerédi


Ícone de esboço Este artigo sobre um(a) matemático(a) é um esboço. Você pode ajudar a Wikipédia expandindo-o.