Article ID Journal Published Year Pages File Type
4648145 Discrete Mathematics 2012 10 Pages PDF
Abstract

A simple   matrix is a (0,1)(0,1)-matrix with no repeated columns. Let FF and AA be (0,1)(0,1)-matrices. We say that AAavoids  FF if there is no submatrix of AA which is a row and column permutation of FF. Let ‖A‖‖A‖ denote the number of columns of AA. We define forb(m,F)=max{‖A‖:A is an m-rowed simple matrix which avoids F}.For two matrices HH and KK, define [H∣K][H∣K] as the concatenation of HH and KK. Let t⋅Ht⋅H denote the concatenation of tt copies of HH. Given a number tt with t≥1t≥1, define F8(t)=[1010010111001100t⋅[10011100]].We are able to show that forb(m,F8(t)) is Θ(m2)Θ(m2) and that this matrix is “maximal” (in some sense) with respect to this property. A conjecture of Anstee and Sali predicts three “maximal” 4-rowed cases to consider with quadratic bounds, and F8(t)F8(t) is one of them. Establishing the quadratic upper bounds for all three cases would establish the veracity of the conjecture for all 4-rowed configurations.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,