TY - JOUR

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

AU - Geneson, Jesse

AU - Tsai, Shen Fu

N1 - Publisher Copyright:
© The authors.

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85095455262&partnerID=8YFLogxK

U2 - 10.37236/7801

DO - 10.37236/7801

M3 - 期刊論文

AN - SCOPUS:85095455262

SN - 1077-8926

VL - 27

SP - 1

EP - 8

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 4

M1 - P4.24

ER -