György Elekes
György Elekes | |
|---|---|
| Född |
19 maj 1949 |
| dog | 29 september 2008 (59 år) |
| Alma mater | Eötvös Loránd University |
| Känd för |
Kombinatorisk geometri Kombinatorisk mängdlära Talteori |
| Vetenskaplig karriär | |
| Fält | Matematik och datavetenskap |
| institutioner | Eötvös Loránd University |
György Elekes (19 maj 1949 – 29 september 2008) var en ungersk matematiker och datavetare som specialiserade sig på kombinatorisk geometri och kombinatorisk mängdteori . Han kan vara mest känd för sitt arbete inom området som så småningom skulle kallas Additive Combinatorics . Särskilt anmärkningsvärt var hans "genialiska" tillämpning av Szemerédi-Trotter-satsen för att förbättra den mest kända nedre gränsen för summaproduktproblemet . Han bevisade också att varje polynom-tidsalgoritm som approximerar volymen av konvexa kroppar måste ha ett multiplikativt fel , och felet växer exponentiellt på dimensionen. Med Micha Sharir satte han upp en ram som så småningom ledde Guth och Katz till lösningen av Erdős distinkta avståndsproblem . (Se nedan.)
Liv
Efter att ha tagit examen från matematikprogrammet vid Fazekas Mihály Gimnázium (dvs. " Fazekas Mihály high school" i Budapest , som är känt för sin spetskompetens, särskilt inom matematik), studerade Elekes matematik vid Eötvös Loránd University . Efter att ha avslutat sin examen började han på fakulteten vid institutionen för analys vid universitetet. 1984 anslöt han sig till den nybildade institutionen för datavetenskap , som leddes av László Lovász . Elekes befordrades till professor 2005. Han fick titeln doktor i matematiska vetenskaper från Ungerska vetenskapsakademin 2001.
Arbete
Elekes började sitt matematiska arbete i kombinatorisk mängdteori , svara på några frågor från Erdős och Hajnal . Ett av hans resultat säger att om mängden av oändliga delmängder av mängden naturliga tal delas upp i otaliga många delar, så finns det i en av dem en lösning av ekvationen A ∪ B = C . Hans intresse bytte senare till ett annat favoritämne för Erdős, diskret geometri och geometrisk algoritmteori . 1986 bevisade han att om en deterministisk polynomalgoritm beräknar ett tal V ( K ) för varje konvex kropp K i något euklidiskt utrymme som ges av ett separationsorakel så att V ( K ) alltid åtminstone vol( K ), volymen av K , sedan för varje tillräckligt stor dimension n finns det en konvex kropp i det n -dimensionella euklidiska rummet så att V ( K )>2 0,99 n vol( K ). Det vill säga, varje polynom-tidsuppskattare av volym över K måste vara felaktig med åtminstone en exponentiell faktor.
Inte långt före sin död utvecklade han nya verktyg inom algebraisk geometri och använde dem för att få resultat i diskret geometri , vilket bevisade Purdys gissning . Micha Sharir organiserade, utökade och publicerade Elekes postuma anteckningar om dessa metoder. Sedan Nets Katz och Larry Guth dem för att lösa (bortsett från en faktor på (log n) 1/2 ) Erdős distinkta avståndsproblem, som uppstod 1946.
