On 0-1 matrices and small excluded submatrices

We say that a 0-1 matrix A avoids another 0-1 matrix (pattern) P if no matrix P′ obtained from P by increasing some of the entries is a submatrix of A. Following the lead of (SIAM J. Discrete Math. 4 (1991) 17-27; J. Combin. Theory Ser. A 55 (1990) 316-320; Discrete Math. 103 (1992) 233-251) and other papers we investigate n by n 0-1 matrices avoiding a pattern P and the maximal number ex(n,P) of 1 entries they can have. Finishing the work of [8] we find the order of magnitude of ex(n,P) for all patterns P with four 1 entries. We also investigate certain collections of excluded patterns. These sets often yield interesting extremal functions different from the functions obtained from any one of the patterns considered.