Endre Szemerédi ( húngaro: [ˈɛndrɛ ˈsɛmɛreːdi] ; nacido el 21 de agosto de 1940) es un matemático e informático húngaro-estadounidense [1] que trabaja en el campo de la combinatoria y la informática teórica . Ha sido profesor de informática del estado de Nueva Jersey en la Universidad de Rutgers desde 1986. También tiene la categoría de profesor emérito en el Instituto de Matemáticas Alfréd Rényi de la Academia de Ciencias de Hungría .
Szemerédi ha ganado premios en matemáticas y ciencias, incluido el Premio Abel en 2012. Ha realizado varios descubrimientos en combinatoria e informática, incluido el teorema de Szemerédi , el lema de regularidad de Szemerédi , el teorema de Erdős-Szemerédi , el teorema de Hajnal-Szemerédi y el teorema de Szemerédi-Trotter .
Szemerédi nació en Budapest . Como sus padres querían que fuera médico, Szemerédi se matriculó en la facultad de medicina, pero la abandonó al cabo de seis meses (en una entrevista [2] lo explicó: "No estaba seguro de poder trabajar con tanta responsabilidad"). ). [3] [4] [5] Estudió en la Facultad de Ciencias de la Universidad Eötvös Loránd de Budapest y recibió su doctorado en la Universidad Estatal de Moscú . Su consejero fue Israel Gelfand . [6] Esto se debió a un error ortográfico, ya que Szemerédi originalmente quería estudiar con Alexander Gelfond . [3]
Szemerédi ha sido profesor de informática del estado de Nueva Jersey en la Universidad de Rutgers desde 1986. Ha ocupado cargos visitantes en la Universidad de Stanford (1974), la Universidad McGill (1980), la Universidad de Carolina del Sur (1981-1983) y la Universidad de Chicago (1985–1986).
Endre Szemerédi ha publicado más de 200 artículos científicos en los campos de las matemáticas discretas, la informática teórica, la combinatoria aritmética y la geometría discreta. Es mejor conocido por su prueba de 1975 de una antigua conjetura de Paul Erdős y Pál Turán : si una secuencia de números naturales tiene una densidad superior positiva , entonces contiene progresiones aritméticas arbitrariamente largas . Esto se conoce ahora como teorema de Szemerédi . Uno de los lemas introducidos en su prueba se conoce ahora como lema de regularidad de Szemerédi , que se ha convertido en un lema importante en combinatoria , utilizándose, por ejemplo, en pruebas de propiedades para gráficos y en la teoría de los límites de los gráficos .
También es conocido por el teorema de Szemerédi-Trotter en geometría de incidencia y el teorema de Hajnal-Szemerédi y el problema de Ruzsa-Szemerédi en teoría de grafos . Miklós Ajtai y Szemerédi demostraron el teorema de las esquinas , un paso importante hacia generalizaciones de dimensiones superiores del teorema de Szemerédi . Con Ajtai y János Komlós demostró el límite superior ct 2 /log t para el número de Ramsey R (3, t ) y construyó una red de clasificación de profundidad óptima. Con Ajtai, Václav Chvátal y Monroe M. Newborn , Szemerédi demostró el famoso lema de cruces, que un gráfico con n vértices y m aristas, donde m > 4 n tiene al menos m 3/64 n 2 cruces . Con Paul Erdős , demostró el teorema de Erdős-Szemerédi sobre el número de sumas y productos en un conjunto finito. Con Wolfgang Paul, Nick Pippenger y William Trotter , estableció una separación entre el tiempo lineal no determinista y el tiempo lineal determinista , en el espíritu del infame problema P versus NP .
Szemerédi ha ganado numerosos premios y distinciones por su contribución a las matemáticas y la informática. Algunos de ellos se enumeran aquí:
Szemerédi es miembro correspondiente (1982) y miembro (1987) de la Academia de Ciencias de Hungría y miembro (2010) de la Academia Nacional de Ciencias de los Estados Unidos . [17] Fue elegido miembro de la Academia Europaea en 2022. [14] También es miembro del Instituto de Estudios Avanzados de Princeton, Nueva Jersey , e investigador permanente en el Instituto de Matemáticas Alfréd Rényi de Budapest. Fue Académico Distinguido Fairchild en el Instituto de Tecnología de California en 1987-1988. Es doctor honoris causa [18] de la Universidad Carolina de Praga. Fue conferenciante en la cuadragésima séptima serie anual de conferencias DeLong [19] en la Universidad de Colorado . También recibió la Cátedra Aisenstadt en CRM, [20] Universidad de Montreal . En 2008 fue profesor Eisenbud en el Instituto de Investigación en Ciencias Matemáticas de Berkeley, California .
En 2012, Szemerédi recibió el Premio Abel "por sus contribuciones fundamentales a las matemáticas discretas y la informática teórica, y en reconocimiento al impacto profundo y duradero de estas contribuciones a la teoría de números aditivos y la teoría ergódica " [21] La mención del Premio Abel también le dio crédito a Szemerédi por llevar la combinatoria al centro del escenario de las matemáticas y destacó su lugar en la tradición de matemáticos húngaros como George Pólya, quien enfatizó un enfoque de resolución de problemas en matemáticas. [22] Szemerédi reaccionó al anuncio diciendo que "no es mi logro personal, sino el reconocimiento a este campo de las matemáticas y a los matemáticos húngaros", lo que le produjo el mayor placer. [23]
Del 2 al 7 de agosto de 2010, el Instituto de Matemáticas Alfréd Rényi y la Sociedad Matemática János Bolyai organizaron una conferencia en honor al 70 cumpleaños de Endre Szemerédi. [24]
Antes de la conferencia, se publicó un volumen de la Serie de Estudios Matemáticos de la Sociedad Bolyai, An Irregular Mind , una colección de artículos editados por Imre Bárány y József Solymosi , para celebrar los logros de Szemerédi con motivo de su 70 cumpleaños. [25] Otra conferencia dedicada a celebrar el trabajo de Szemerédi es la Tercera Conferencia Abel: Una celebración matemática de Endre Szemerédi. [26]
Szemerédi está casado con Anna Kepes; tienen cinco hijos, Andrea, Anita, Peter, Kati y Zsuzsi. [19] [27]