György Elekes (19 de mayo de 1949 – 29 de septiembre de 2008) [1] fue un matemático y científico informático húngaro que se especializó en geometría combinatoria y teoría de conjuntos combinatorios . Es posible que sea más conocido por su trabajo en el campo que eventualmente se llamaría Combinatoria aditiva . Particularmente notable fue su "ingeniosa" [2] aplicación del teorema de Szemerédi-Trotter para mejorar el límite inferior más conocido para el problema de suma-producto . [3] También demostró que cualquier algoritmo de tiempo polinomial que se aproxime al volumen de cuerpos convexos debe tener un error multiplicativo , y el error crece exponencialmente en la dimensión. [4] Con Micha Sharir estableció un marco que finalmente llevó a Guth y Katz a la solución del problema de distancias distintas de Erdős . [5] (Véase más abajo.)
Después de graduarse del programa de matemáticas en el Fazekas Mihály Gimnázium (es decir, " escuela secundaria Fazekas Mihály " en Budapest , que es conocida por su excelencia, especialmente en matemáticas), Elekes estudió matemáticas en la Universidad Eötvös Loránd . Al completar su título, se unió a la facultad en el Departamento de Análisis de la universidad. En 1984, se unió al recién formado Departamento de Ciencias de la Computación , que estaba siendo dirigido por László Lovász . Elekes fue promovido a profesor titular en 2005. Recibió el título de Doctor en Ciencias Matemáticas de la Academia Húngara de Ciencias en 2001. [1]
Elekes comenzó su trabajo matemático en la teoría de conjuntos combinatorios , respondiendo algunas preguntas planteadas por Erdős y Hajnal . Uno de sus resultados establece que si el conjunto de subconjuntos infinitos del conjunto de números naturales se divide en un número contable de partes, entonces en una de ellas, hay una solución de la ecuación A ∪ B = C. [1] [6] Su interés más tarde cambió a otro tema favorito de Erdős, la geometría discreta y la teoría de algoritmos geométricos . En 1986 demostró que si un algoritmo polinomial determinista calcula un número V ( K ) para cada cuerpo convexo K en cualquier espacio euclidiano dado por un oráculo de separación tal que V ( K ) siempre al menos vol( K ), el volumen de K , entonces para cada dimensión suficientemente grande n , hay un cuerpo convexo en el espacio euclidiano n -dimensional tal que V ( K )>2 0.99 n vol( K ). Es decir, cualquier estimador de volumen en tiempo polinomial sobre K debe ser inexacto al menos en un factor exponencial. [1] [4]
Poco antes de su muerte, desarrolló nuevas herramientas en geometría algebraica y las utilizó para obtener resultados en geometría discreta , demostrando la conjetura de Purdy . Micha Sharir organizó, amplió y publicó las notas póstumas de Elekes sobre estos métodos. [7] Luego , Nets Katz y Larry Guth los utilizaron para resolver (aparte de un factor de (log n) 1/2 ) el problema de distancias distintas de Erdős , planteado en 1946. [5] [8]