Discrete Geometry Group

Rafael Gillmann (fka. Rafael Mechtel)

Address

Technische Universität Berlin
Fakultät II: Institut für Mathematik, MA 6-2,
Straße des 17. Juni 136
10623 Berlin
Germany

The math-building.

Member of the Discrete Geometry Group headed by Prof. Günter M. Ziegler part of the Institute of Mathematics of the Technische Universität Berlin

Member of the DFG Research Group Algorithms, Structure, Randomness
Project 6: Geometry and combinatorics of 0/1-polytopes

I am also closely associated to the combinatorial optimization department of the Zuse Institut Berlin, where I was a guest during February and March 2005.

Research Interests

My research interests are located between combinatorics, geometry, and optimization. So far, I have spent most of my research-time with the following two projects.

Geometry and combinatorics of 0/1-polytopes
To a large extent, successes in combinatorial optimization in the last few decades have been based upon insights into the geometry of the polytopes corresponding to the various combinatorial problems. Such a polytope is, as a rule, the convex hull of the characteristic vectors of the considered combinatorial objects (e.g. subsets of edges in a graph, which are matchings). While the structure of numerous special classes of 0/1-polytopes (convex hulls of points with 0/1-coordinates) has been studied intensively, to date there is very little known about the general class of 0/1-polytopes.
In this project Prof. Volker Kaibel and I investigate random 0/1-polytopes and other classes of 0/1-polytopes in order to obtain general structural knowledge about the overall class of 0/1-polytopes. In particular we look at:

• Graphs of random 0/1-polytopes
• Face densities of random 0/1-polytopes
• Expansion properties

The random edge simplex algorithm
The simplex algorithm is the oldest linear programming algorithm. In terms of geometry it finds the minimal vertex of the given simple d-Polytope by starting at a given starting vertex and iteratively moving to an improving neighbor until the minimal vertex is reached. But how to choose the improving neighbor?
The random edge rule chooses the next next vertex uniformly at random among all improving neighbors. The price for its simplicity is that it does not use any combinatorial or geometric information specific to polytopes. Thus it seems reasonable that obtaining good upper bounds on the running time of random edge might be difficult.
In this project I investigate random edge on three and four dimensional polytopes to obtain new insights on how polytope specific structures can be used to analyze random edge. In particular I look at:

• Specific 4-dimensional polytopes: dual cyclic polytopes and products of two polygons
• Simple 3-dimensional polytopes
  (Also with: Volker Kaibel, Gabriel Nivasch, Micha Sharir, and Günter M. Ziegler)

Publications

• The Random Edge Simplex Algorithm on Dual Cyclic 4-Polytopes (arXiv:math.CO/0605117)
  Preprint, 32 pages, May 2006
  
• Revlex-Initial 0/1-Polytopes (arXiv:math.CO/0412028)
  with Volker Kaibel
  Preprint, 26 pages, December 2004
  appeared in Journal of Combinatorial Theory, Series A 112(5):799-821, July 2006
• The Simplex Algorithm in Dimension Three (arXiv:math.CO/0309351)
  with Volker Kaibel, Micha Sharir, and Günter M. Ziegler
  Preprint, 24 pages, September 2003,
  appeared in SIAM J. on Computing, 34(2):475-497, 2005
  There is also a previous version available as arXiv:math.CO/0301076.
• Randomized Pivot Rules for the Simplex Algorithm on Three-Dimensional Problems (ps, pdf)
  Diploma Thesis, 92 pages, July 2003, Supervisor: Günter M. Ziegler

In preparation (coming soon)

• Neighborliness of random 0/1-polytopes
• A class of 0/1-polytopes with exponentially small vertex-expansion

If you have any questions concerning my publications, please do not hesitate to contact me.

Teaching

In the summer semester of 2005 I taught the exercise sessions of the four hour a week lecture Fortgeschrittene Methoden der Ganzzahligen Linearen Programmierung (advanced methods of integer programming) held by Volker Kaibel and Thorsten Theobald.

The exercises are still available on the home-page of the course.