In this paper we study the extremal problem of finding how many 1 entries an n by n 0-1 matrix can have if it does not contain certain forbidden patterns as submatrices. We call the number of I entries of a 0-1 matrix its weight. The extremal function of a pattern is the maximum weight of an n by n 0-1 matrix that does not contain this pattern as a submatrix. We call a pattern (a 0-1 matrix) linear if its extremal function is O(n). Our main results are modest steps towards the elusive goal of characterizing linear patterns. We find novel ways to generate new linear patterns from known ones and use this to prove the linearity of some patterns. We also find the first minimal non-linear pattern of weight above 4. We also propose an infinite sequence of patterns that we conjecture to be minimal non-linear but have Omega(n logn) as their extremal function. We prove a weaker statement only, namely that there are infinitely many minimal not quasi-linear patterns among the submatrices of these matrices. For the definition of these terms see below. (C) 2008 Elsevier Inc. All rights reserved.
展开▼
