An Extremal Problem on Sparse 0-1 Matrices

Abstract

The problem of estimating the number of 1’s in a square 0-1 matrix with certain forbidden configurations is considered, and nearly tight bounds are provided. This is motivated by a problem in computational geometry.