Bounds on parameters of minimally non-linear patterns

Abstract

Let $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 $ex(n,P)=\omega (n)$ but $ex(n,P^{\prime })=O(n)$ for every strict subpattern $P^{\prime }$ 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 $e{x}_{<}(n,G)$, which is the maximum possible number of edges in any ordered graph on $n$ vertices with no ordered subgraph isomorphic to $G$.

13 pages

References in corpus (1)

• Extremal problems in ordered graphs