Bounds on parameters of minimally nonlinear patterns (Q1691099)

Summary: Let \(\mathrm{ex}(n, P)\) be the maximum possible number of ones in any 0-1 matrix of dimensions \(n \times n\) that avoids \(P\). Matrix \(P\) is called minimally non-linear if \(\mathrm{ex}(n, P) \neq O(n)\) but \(\mathrm{ex}(n, P') = O(n)\) for every proper subpattern \(P'\) of \(P\). We prove that the ratio between the length and width of any minimally non-linear 0-1 matrix is at most \(4\), and that a minimally non-linear 0-1 matrix with \(k\) rows has at most \(5k-3\) ones. We also obtain an upper bound on the number of minimally non-linear 0-1 matrices with \(k\) rows. In addition, we prove corresponding bounds for minimally non-linear ordered graphs. The minimal non-linearity that we investigate for ordered graphs is for the extremal function \(\operatorname{ex}_{<}(n, G)\), which is the maximum possible number of edges in any ordered graph on \(n\) vertices with no ordered subgraph isomorphic to \(G\).