کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648145 1342394 2012 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Evidence for a forbidden configuration conjecture: One more case solved
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Evidence for a forbidden configuration conjecture: One more case solved
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 17, 6 September 2012, Pages 2720–2729
نویسندگان
, , ,