Widths and Heights of (0,1) -Matrices
D. R. Fulkerson, H. J. Ryser · Canadian Journal of Mathematics · 1961
A number of combinatorial problems may be regarded as particular instances of the following rather general situation. Given a setXcomposed ofnelements x1, x2, ..., xn, andmsubsets X1X2, … ,XmofX, find a minimal system of representatives forX1, X2, … ,Xm. That is, single out a subset X* ofXsuch thatXi∩ X* is non-empty fori = 1,2, … ,m, and no subset ofXcontaining fewer elements than X* has this property. To illustrate, each of the following can be thought of in these terms.