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!
Best Answer
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).