Zur Seite der TU

Seminar: Proof Techniques in Polyhedral Combinatorics

Zur Seite des Instituts für Mathematik

 

Winter Semester 2011/2012

 
LV-Nr.: 3236 L 321
 
Prof. Dr. Dr. h.c. mult. Martin Grötschel
 




News

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.

Contents

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.


Timing

The seminar will be organized as a block seminar. The initial meeting of the seminar (Vorbesprechung) took place on
Friday, October 28, 2011 at 12:00 h
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)
.
The final seminar schedule with the sequence of all presentations will be announced about one week in advance of the seminar.

Registration

Students interested in participating in the seminar are invited to send an email to Annie Raymond (raymond@zib.de), who will be in charge of organizing this seminar.

Seminar Requirements

Every participant is expected to attend all presentations of the seminar. Every participant is also required to produce a handout of about 5 pages summarizing the content of their own lecture. This handout is supposed to be produced in good layout quality (some version of TeX is recommended). All handouts will be distributed to all participants by e-mail before the seminar. All participants are free to choose their own lecture style. Blackboards, an overhead projector and a beamer will be available in ZIB's seminar room. The lectures should last about 60 minutes. Basic knowledge in Graph Theory and Linear and Integer Programming, such as taught in ADM I and II, is a prerequisite for this seminar.


Contact


   
consultation-hours
room phone email
Office at TU Berlin: Martin Grötschel on appointment Room: MA 302 314-23266 Please use: groetschelzib.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





Literature

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.




Last changes: December 12, 2011