Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I just went to a graph theory talk talking about various fractional graph parameters (but focusing on one). These were defined using linear programming. A question was asked, "How can we learn more about this technique." The answer given was, "There is not really a good resource for linear programming in combinatorics/graph theory." He said Schrijver (spelling?) has a book but you'd have to wade through a lot of stuff to get the stuff that is most important to graph theory/combinatorics.

So, do any of you know of good references that are specifically geared toward graph theory/combinatorics? It could be a book, chapter of a book, paper, whatever. Thanks for any help!

share|cite|improve this question
You can read the chapter on Polyhedral Combinarorics in the Handbook of combinatorics by Schrijver. – Shahab Nov 9 '11 at 12:44
up vote 3 down vote accepted

I like this book Understanding and Using Linear Programming by Bernd Gärtner and Jiří Matoušek, and I think most of the material has a combinatorial flavour (published in 2006 - this book is quite recent!). However it is mostly softball stuff (aimed at beginners). If you look at what the coauthor Jiří Matoušek has published you also find a book with the title Using the Borsuk-Ulam theorem. At first glance this will appear as having nothing to do with linear programming, however there is at least one intersection: The Borsuk Ulam theorem is very general (you can derive Brouwers fixed point theorem from it for example), but you can also derive very simple 'clearly combinatorial' things like the ham-sandwich theorem. This theorem appears in the 2D variant of the fastest algorithm for 'least absolute deviations', elaborated on in this article by William Steiger, which is almost equivalent to linear programming (I mean 'least absolute deviations' is almost equivalent to linear programming - but I don't know an algorithm beyond 2D for LAD that uses the ham-sandwich theorem effectively - which of course doesn't say much).

share|cite|improve this answer

Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics) (ISBN-13: 978-3642244872) and Combinatorial Optimization: Polyhedra and Efficiency (Algorithms and Combinatorics) (ISBN-13: 978-3540443896)

The first as general introduction and enough for most cases, the latter as reference material covering basically the whole topic

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.