Endre Szemerédi
Endre Szemerédi (Budapeste, 21 de agosto de 1940) é um matemático húngaro.
| Endre Szemerédi | |
|---|---|
 | |
| Nascimento | 21 de agosto de 1940 (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 |
Vida editar
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
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
Referências
- ↑ Endre Szemerédi (em inglês) no Mathematics Genealogy Project
Ligações externas editar
- Página pessoalno Instituto de Matemática Alfréd Rényi
