Discrete Mathematics and Theoretical Computer Science

TITLE: "POLYHEDRAL COMBINATORICS"

EDITORS: William Cook and Paul D. Seymour

Published by the American Mathematical Society

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the
AMS Bookstore and
order directly from there.
DIMACS ** does not** distribute or sell these books.

This collection of papers constitutes the proceedings of a workshop on polyhedral combinatorics, held from 12th to 16th June 1989, in the Headquarters Plaza Hotel, Morristown, New Jersey. Two series of lectures were given by L. Lovasz and A. Schrijver (a total of three one-hour lectures each), and there were a number of shorter lectures. The meeting was the first in a series of workshops supported by DIMACS (the center for Discrete Mathematics and Theoretical Computer Science). DIMACS is an NSF Science and Technology Center, and it is a collaboration of Bellcore, AT&T Bell Labs, Rutgers University, and Princeton University. We would like to express our thanks to DIMACS and the NSF for their generous support.

All of the papers have been refereed. We have tried to organize the volume as far as possible so that related papers are near to one another.

We regret the death of Martin Farber (AT&T Bell Labs) shortly before the workshop. Martin was a leading figure in polyhedral combinatorics, and this volume includes an orbituary by Pavol Hell.

Matrix Cones, Projection Representations, and Stable Set Polyhedra L. Lovasz and A. Schrijver 1 A Generalization of Lovasz's 0 Function Giri Narasimhan and Rachel Manber 19 On Cutting Planes and Matrices A.M.H. Gerards 29 Random Volumes in the n-Cube M.E. Dyer, Z. Furedi, and C. McDiarmid 33 Test Sets for Integer Programs, 0_ Sentences Ravi Kannan 39 Solvable Classes of Generalized Traveling Salesman Polytope S.N. Kabadi and R. Chandrasekaran 49 Handles and Teeth in the Symmetric Traveling Salesman Problems Denis Naddef 61 On the Complexity of Branch and Cut Methods for the Traveling Salesman Problem W. Cook and M. Hartmann 75 Existentially Polytime Theorems Kathie Cameron and Jack Edmonds 83 The Width-Length Inequality and Degenerate Projective Planes Alfred Lehman 101 On Lehman's Width-Length Characterization P.D. Seymour 107 Applications of Polyhedral Combinatorics to Multicommodity Flows and Compact Surfaces A. Schrijver 119 Vertex-Disjoint Simple Paths of Given Homotopy in a Planar Graph A. Frank and A. Schrijver 139 On Disjoint Homotopic Paths in the Plane Andras Frank 163 On the Complexity of the Disjoint Paths Problem (Extended Abstract) Matthias Middendorf and Frank, Pfeiffer 171 The Paths-Selection 179 Matthias Middendorf and Frank Pfeiffer Planar Multicommodity Flows, Max Cut, and the Chinese Postman Problem Francisco Barahona 189 The Cographic Multiflow Problem: An Epilogue Andras Sebo 203 Exact Edge-Colorings of Graphs without Prescribed Minors Odile Marcotte 235 On the Chromatic Index of Multigraphs and a Conjecture of Seymour, (II) Odile Marcotte 245 Spanning Trees of Different Weights A. Schrijver and P.D. Seymour 281

Index of Volumes

DIMACS Homepage

Contacting the Center

Document last modified on October 28, 1998.