Max-Min Theorems in Combinatorial Theory

Robert E. Tarjan

Introduction

There is a class of theorems in combinatorial theory in which it is asserted that the maximum size of a certain structure is equal to the minimum size of another structure. Examples of such theorems are the König-Egerváry theorem, Dilworth's theorem, and the max-flow-min-cut theorem of Ford and Fulkerson. We wish to set these theorems in a general framework, to extend the know results, and to state some new conjectures.