Sharper bounds and structural results for minimally nonlinear 0-1 matrices (Q2209895): Difference between revisions

Summary: The extremal function \(\operatorname{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 \(\operatorname{ex}(n, P) = \omega(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 nonlinear 0-1 matrix with \(k\) rows were found in [\textit{P. A. CrowdMath}, Electron. J. Comb. 25, No. 1, Research Paper P1.5, 11 p. (2018; Zbl 1386.05191)]. 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.