Sharper bounds and structural results for minimally nonlinear 0-1 matrices

The extremal function ex(n, P) is the maximum possible number of ones in any 0-1 matrix with n rows and n columns that avoids P. A 0-1 matrix P is called minimally nonlinear if ex(n, P) = ω(n) but ex(n, P^′) = O(n) for every P^′ that is contained in P but not equal to P. Bounds on the number of ones and the number of columns in a minimally non-linear 0-1 matrix with k rows were found in (CrowdMath, 2018). In this paper, we improve the upper bound on the number of ones in a minimally nonlinear 0-1 matrix with k rows from 5k − 3 to 4k − 4. As a corollary, this improves the upper bound on the number of columns in a minimally nonlinear 0-1 matrix with k rows from 4k − 2 to 4k − 4. We also prove that there are not more than four ones in the top and bottom rows of a minimally nonlinear matrix and that there are not more than six ones in any other row of a minimally nonlinear matrix. Furthermore, we prove that if a minimally nonlinear 0-1 matrix has ones in the same row with exactly d columns between them, then within these columns there are at most 2d − 1 rows above and 2d − 1 rows below with ones.