Forbidden configurations: Boundary cases
Por:
Anstee R.P., Raggi M., Sali A.
Publicada:
1 ene 2013
Resumen:
A simple matrix is a {0, 1} -matrix with no repeated columns. For a {0, 1} -matrix F, define F ? A if there is a submatrix of A which is a row and column permutation of F. Let {norm of matrix}A {norm of matrix} denote the number of columns of A. Define forb(m,F)=max{{norm of matrix}A{norm of matrix}:A is m-rowedsimplematrixand F{does not precede}A}. We classify all 6-rowed configurations F for which forb (m, F) is ? (m2) and prove forb (m, F) is ? (m3) for all other 6-rowed F. We also prove that forb (m, G) is O (m2) for a particular 5 × 6 simple G and the addition of any column ? to G makes forb (m, [G?]) to be ? (m3) The results are evidence for a conjecture of Anstee and Sali which predicts the growth rate of forb (m, F) as a function of F. © 2013 Elsevier Ltd.
|