Endre Szemerédi
Endre Szemerédi | |
---|---|
Nascimento | 21 de agostode1940(83 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 agostode1940) é ummatemáticohúngaro.
Vida[editar|editar código-fonte]
Nasceu emBudapeste,estudou naUniversidade Eötvös Lorándem Budapeste e obteve o doutorado naUniversidade Estatal de Moscou,orientado porIsrael Gelfand.[1]
Trabalha nos campos dacombinatóriae ciência computacional teórica. É desde 1986 professor daUniversidade Rutgers.Foi professor visitante naUniversidade Stanford(1974),Universidade McGill(1980),Universidade da Carolina do Sul(1981–1983) eUniversidade 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 paragrafose 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 Ajtaie 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 dect2/logt para onúmero de RamseyR(3,t), e construiu uma rede de classificação de profundidade ótima. Com Ajtai,Václav Chvátale Monroe M. Newborn, Szemerédi provaram o famoso lema de cruzamento, que um grafo comnvértices emarestas, ondem> 4ntem pelo menosm3/ 64n2cruzamentos. ComPaul 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
- ↑Endre Szemerédi(em inglês) noMathematics Genealogy Project
Ligações externas[editar|editar código-fonte]
- Página pessoalno Instituto de Matemática Alfréd Rényi