Seminar: Proof Techniques in Polyhedral Combinatorics
|
|
Seminar: Proof Techniques in Polyhedral Combinatorics |
|
Winter Semester 2011/2012 |
In the winter semester 2011/2012 I will offer (supported by Annie Raymond) a seminar with the title: "Proof Techniques in Polyhedral Combinatorics". The seminar will be held in English.
Usual seminars address particular mathematical topics and have as a main challenge to present important results. The focus of this seminar is not on results, but on proof ideas. Polyhedral combinatorics is a "mathematical technology" which is frequently employed to design cutting plane algorithms and the like for solving combinatorial optimization problems. The idea here is to transform a combinatorial problem into a geometrical problem by looking at the polyhedron (or polytope) associated to a combinatorial optimization problem, i.e. by investigating the polyhedron defined as the convex hull of the incident vectors of all feasible solutions of the combinatorial problem. When using techniques of linear programming for solving a combinatorial problem, properties of the associated polyhedron need to be studied. The first step is typically to determine the dimension of the polyhedron under investigation. Then facet defining inequalities have to be found as well as a complete characterization (usually for special cases) by means of systems of linear inequalities. The adjacency of vertices may be of interest, and the like. Moreover, for computational aspects, it is important to design good separation algorithms. Polyhedral combinatorics has grown considerably in the last 50 years or so, and many proof techniques have evolved. It is interesting to observe that in many cases one proof technique gives rise to a short and concise proof, while another leads to long and tedious arguments. In this seminar, each student will present a lecture that will focus on one such proof technique. The student will explain the technique in general and then give several examples of applications of the technique under investigation. Examples of polyhedra arising in polyhedral combinatorics that will be treated in this seminar are matroid polytopes, the traveling salesman polytope, matching and b-matching polytopes, stable set polytopes, cut polytopes, etc.
Friday, October 28, 2011 at 12:00 hThe final seminar schedule with the sequence of all presentations will be announced about one week in advance of the seminar.
in room TU MA 315 (MATHEON Lounge).
Short introduction lectures on the seminar topics were presented by the participants on
Friday, December 09, 2011, at 12:00 h
in room TU MA 315 (MATHEON Lounge).
The block seminar itself, where each student will give a presentation of about one hour length, will take place on
Friday, February 17 and Saturday, February 18, 2012
in the seminar room (room 2006) of the Zuse Institute (ZIB).
|
|
room | phone | |||
| Office at TU Berlin: | Martin Grötschel | on appointment | Room: MA 302 | 314-23266 | Please use: groetschel zib.de |
| Office at Zuse Institute: | Martin Grötschel | on appointment | Room: 3025 | 84185 210 | groetschelzib.de |
| Office at Zuse Institute: | Annie Raymond | on appointment | Room: 3024 | 84185 448 | raymondzib.de |
| Secretariat (TU): | Claudia Ewel | on appointment | MA 310 | 314-28 478 | ewelmath.tu-berlin.de |
| Secretariat (ZIB): | Bettina Kasse | on appointment | 3025 | 84185-209 | kassezib.de |
Basic knowledge in Graph Theory and Linear and Integer Programming, such as taught in ADM I and II, is a prerequisite for this seminar. An excellent book where almost all proof techniques employed in polyhedral combinatorics are used (but without describing the techniques explicitly) is: Alexander Schrijver, Combinatorial Optimization (3 Volumes, A, B, C) A set of references to be studied will be provided for each individual lecture at the first seminar meeting in October.