Gil Kalai

Gil Kalai 2007 in Oberwolfach

Gil Kalai 1986

Gil Kalai (hebräisch גיל קלעי; * 1955 in Tel Aviv) ist ein israelischer Mathematiker und Informatiker, der sich mit Algorithmen zum Beispiel der Linearen Programmierung und Kombinatorik beschäftigt.

Leben

Kalai promovierte 1983 an der Hebrew University bei Micha Perles und war danach als Post-Doc am Massachusetts Institute of Technology. Ab 1985 war er an der Hebrew University, wo er 1993 eine volle Professur erhielt. Gleichzeitig ist er Adjunct Professor für Informatik und Mathematik an der Yale University. 1994 war er Milliman Lecturer an der University of Washington. Er war unter anderem Gastwissenschaftler und Gastprofessor am Institute for Advanced Study (1995) und bei IBM in San Jose (1991/92).

Er ist Herausgeber des Israel Journal of Mathematics. 1992 erhielt er den Pólya-Preis der SIAM, 1993 den Erdős-Preis der israelischen mathematischen Gesellschaft, 1994 den Fulkerson-Preis. 1994 war er Invited Speaker auf dem Internationalen Mathematikerkongress in Zürich (Combinatorics and convexity). 2015 wurde er in die Academia Europaea gewählt. 2016 hielt er einen Plenarvortrag auf dem Europäischen Mathematikerkongress (Combinatorics of boolean functions and more).

Wirken

Kalai ist bekannt dafür, dass er Varianten des Simplex-Algorithmus fand, die in subexponentieller Zeit laufen. Mit Ehud Friedgut bewies er 1996, dass jede monotone Eigenschaft von Graphen einen scharfen Phasenübergang besitzt (bei Variation der Größe des Graphen, der Anzahl der Knoten). 1993 widerlegte er mit Jeff Kahn eine Vermutung von Karol Borsuk über die Anzahl $f(d)$ der Teile (als Funktion der Dimension $d$), die nötig sind, um konvexe Mengen im $\mathbb {R} ^{d}$ in Teilmengen mit kleinerem Durchmesser zu zerlegen. Borsuk vermutete $f(d)=d+1$, Kalai und Kahn bewiesen $f(d)\geq 1{,}2^{\sqrt {d}}$ für hinreichend große $d$.

Die $3^{d}$-Vermutung von Kalai besagt, dass jedes d-dimensionale zentralsymmetrische Polytop mindestens $3^{d}$ Seiten hat (wobei Ecken, Kanten, Seitenflächen, … und auch das gesamte Polytop als Seiten mitgezählt werden). Zum Beispiel gilt in $d=2$ für das Parallelogramm $4+4+1=9=3^{2}$ und für den Kubus in $d=3$ gilt $8+12+6+1=27=3^{3}$. Der allgemeine Fall ist offen (in vier und weniger Dimensionen ist die Vermutung bewiesen, ebenso für simpliziale Polytope).

Weblinks

• Homepage
• Sein Blog Combinatorics and more
• Biografie an der Universität Eindhoven