کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648145 | 1342394 | 2012 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Evidence for a forbidden configuration conjecture: One more case solved Evidence for a forbidden configuration conjecture: One more case solved](/preview/png/4648145.png)
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.
Journal: Discrete Mathematics - Volume 312, Issue 17, 6 September 2012, Pages 2720–2729