DMV Logo
Fachgruppe Diskrete Mathematik

Heidi Gebauer erhält Richard-Rado-Preis 2012


v.l.n.r.: Heidi Gebauer, Michel Goemans, Juliane Dunkel

Der Richard-Rado-Preis 2012 der Fachgruppe Diskrete Mathematik der DMV wurde im Rahmen des "Symposiums Diskrete Mathematik" an der TU Berlin am Samstag, 18. August 2012, vergeben an:

Heidi Gebauer (ETH Zürich) für ihre Dissertation über kombinatorische Spiele bei Tibor Szabó (FU Berlin) und Emo Welzl (ETH Zürich). Juror Michel Goemans würdigte ihre hervorragende Doktorarbeit, in der sie Antworten zu etlichen der "The 7 most humiliating open problems" aus dem Buch von Jozsef Beck über kombinatorische Spiele (2008) gefunden hat.

Eine "Honorable Mention" ging an Juliane Dunkel (MIT) für ihre Promotion über den Chvatal-Gormory-Abschluss in der ganzzahligen Optimierung. Juliane Dunkel kommt ursprünglich von der TU Berlin, hat am MIT bei Andreas Schulz (ebenfalls vorm. TU Berlin) promoviert.

Laudatio von Michel Goemans zur Preisverleihung an Heidi Gebauer und Juliane Dunkel:

Maker-Breaker games are two-person combinatorial games in which Maker tries to build a subgraph with certain properties by fixing edges while Breaker tries to prevent it from happening by deleting edges. In her dissertation, Heidi Gebauer tackles several of the most humiliating open problems in the area, an adjective coined by Joszef Beck in his reference book on the subject. Among several other results, she resolves the long-standing threshold question for the biased connectivity game in the affirmative, shows the counterintuitive result that Maker can do better in the clique game if both players can select 6 or more edges at a time, and refutes the strongest form of the Neighborhood conjecture with consequences to the satisfiability of Boolean formulas. For these contributions to combinatorial game theory, Heidi Gebauer is eminently deserving of the 2012 Richard Rado prize awarded by the Discrete Mathematics section of the German mathematical Society.

Cutting planes constitute one of the most fundamental tools in integer programming. In particular, the Gomory-Chvátal closure provides an automatic strengthening of any polyhedron towards its integer hull. In her dissertation, Juliane Dunkel proves that the closure of a possibly non-rational polytope is always a rational polytope. This answers in the affirmative a long-standing question left open by Lex Schrijver in a seminal paper over 30 years ago, in which he showed that the closure of any rational polyhedron is always rational. She also introduces a strengthening of the Gomory-Chvátal closure in her dissertation. For these contributions to the theory of cutting planes, Juliane Dunkel is eminently deserving of an Honorable Mention for the 2012 Richard Rado prize.

Der Richard-Rado-Preis wurde von Fachgruppe Diskrete Mathematik der DMV zum achten Mal für hervorragende Dissertationen in der Diskreten Mathematik vergeben. Der Preis wird vom Springer Verlag gestiftet und ist in diesem Jahr mit EUR 1000,- dotiert.

Text: Thomas Vogt; Foto: Jannik Matuschke