Define the 1-width of a 0-1 matrix A to be the minimum number of columns that can be selected from A such that all the row sums of the resulting submatrix of A are at least 1. If \(A_ n\) is the incidence matrix of a Steiner triple system on n points, it can be checked that for \(n\leq 15\) the 1-width of \(A_ n\) is less than 2(n-1)/3. In order to disprove this possible upper bound, D. R. Fulkerson, G. L. Nemhauser and L. E. Trotter jun. [Two computationally difficult set covering problems that arise in computing the 1-width of incidence matrices of Steiner triple systems, Math. Program. Study 2, 72-81 (1974; Zbl 0353.90060)] constructed matrices of Steiner triple systems of orders 27 and 45, \(A_{27}\) and \(A_{45}\), respectively. They showed that \(A_{27}\) could not be covered in 17 columns and thus the upper bound of 2(n-1)/3 was not correct. However they could not compute the 1-width of the matrix \(A_{45}\) as it was too large for their integer programming techniques. Several years later it was proven that the 1-width of \(A_{45}\) equals 30. In this paper the author also finds that the 1-width of \(A_{45}\) is 30 by giving a computer algorithm which takes into account more of the structure of the matrix \(A_{45}.\)
The author then proceeds to use the matrix \(A_{45}\) to construct a matrix \(A_{135}\) (the incidence matrix of an STS(135)) which has no cover of 90 columns. Thus the upper bound for the 1-width of a Steiner triple system on n points must be strictly greater than 2n/3.
Finally this paper discusses the so called “chess queen graph” which has \(n^ 2\) vertices and two vertices are adjacent if the corresponding cells on an n by n chessboard can reach each other via a single move of a queen. The paper lists solutions for \(n\leq 12\). The paper concludes with a listing of the computer code for the 1-width problem and the chess queen graph problem.