Maximum 4-block-free matrices and knapsack-type relaxations

A 0-1 matrix is called l-block-free if it nowhere has a pair of rows ancl a pair of columns such that the four entries thus singled out are all 1,s. What is the maximum number of 1's a 4-block-free matrix can have? We investigate a knapsack-type relaxation of a 0-1 prograrnming formulatiotr of the problcm, accotrnt for its solution properties ancl acldress issues as to t,he realizobility in terms of 0-1 matrices of the solutions found. We note frtrt,hermore that a conclusivc answer, valicl fclr all square rrratrices, would also settle the cla.ssical anrl gelrerally unanswered question as to ttle existence of a so-called finite projectiue plane of a given order. Along the way, some surprisingly simple proofs of earlier results arc provided. Also a nerv characlerization of a finite projective plane is given.