|
Endre Szemerédi
Endre Szemerédi (Budapeste, 21 de agosto de 1940) é um matemático húngaro. VidaNasceu 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). TrabalhoEndre 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émReferências
Ligações externas
|
||||||||||||||||||||
