Bounds on parameters of minimally non-linear patterns
PA CrowdMath - arXiv preprint arXiv:1701.00706, 2016 - arxiv.org
PA CrowdMath
arXiv preprint arXiv:1701.00706, 2016•arxiv.orgLet $ 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')= O (n) $ for every strict 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 $5 k-3$ ones. We also obtain
an upper bound on the number of minimally non-linear 0-1 matrices with $ k $ rows. In …
n\times n $ that avoids $ P $. Matrix $ P $ is called minimally non-linear if $ ex (n, P)=\omega
(n) $ but $ ex (n, P')= O (n) $ for every strict 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 $5 k-3$ ones. We also obtain
an upper bound on the number of minimally non-linear 0-1 matrices with $ k $ rows. In …
Let be the maximum possible number of ones in any 0-1 matrix of dimensions that avoids . Matrix is called minimally non-linear if but for every strict subpattern of . We prove that the ratio between the length and width of any minimally non-linear 0-1 matrix is at most , and that a minimally non-linear 0-1 matrix with rows has at most ones. We also obtain an upper bound on the number of minimally non-linear 0-1 matrices with 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 , which is the maximum possible number of edges in any ordered graph on vertices with no ordered subgraph isomorphic to .
arxiv.org