Can anyone suggest a text on polyhedral theory? Particularly on increasing the number of faces under projections. 0,1 polytopes
3 Answers
$\begingroup$
$\endgroup$
Reading between the lines of your comment about increasing the number of faces under projections, I'm guessing that you're interested in the subject known as "extension complexity." Starting with some complicated polytope like the traveling salesman polytope, one wants to know if it is the projection of a much simpler polytope in slightly higher dimension. This recent paper by Fiorini et al. has a lot of relevant references. This is an active research area so I think there is no single book that really covers the area properly.
But if you're instead looking for a general textbook treatment of polyhedral theory in the context of combinatorial optimization, a standard reference is Schrijver's magnum opus Combinatorial Optimization: Polyhedra and Efficiency.
$\begingroup$
$\endgroup$
0
General references on polytopes are:
- Ziegler: Lecture on Polytopes (already mentioned by Joseph O'Rourke in a comment)
- Grünbaum: Convex Polytopes
- Thomas: Lectures in Geometric Combinatorics
- Bronsted: An introduction to convex polytopes
- Matousek: Lectures on Discrete Geometry, Chapter 5
- Barvinok: A Course in Convexity, Chapter VI
A interesting survey about 0/1 polytopes was written by Ziegler in 2000 and appeared in "Polytopes -- Combinatorics and Computation" published by Birkhäuser (in the DMV Seminar series).
A paper that might be of interest to you is Rothvoß: Some 0/1 polytopes need exponential size extended formulations.
$\begingroup$
$\endgroup$
For me, the classical reference on polyhedral theory is Schrijver's 'Theory of Linear and Integer Programming', together with the Combinatorial Optimization monograph that was mentioned above.
If you have a more specific concern, please specify your question.