کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648213 1342398 2012 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On avoiding some families of arrays
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On avoiding some families of arrays
چکیده انگلیسی

An n×nn×n array AA with entries from {1,…,n}{1,…,n} is avoidable   if there is an n×nn×n Latin square LL such that no cell in LL contains a symbol that occurs in the corresponding cell in AA. We show that the problem of determining whether an array that contains at most two entries per cell is avoidable is NPNP-complete, even in the case when the array has entries from only two distinct symbols. Assuming that P≠NPP≠NP, this disproves a conjecture by Öhman. Furthermore, we present several new families of avoidable arrays. In particular, every single entry array (arrays where each cell contains at most one symbol) of order n≥2kn≥2k with entries from at most kk distinct symbols and where each symbol occurs in at most n−2n−2 cells is avoidable, and every single entry array of order nn, where each of the symbols 1,…,n1,…,n occurs in at most ⌊n5⌋ cells, is avoidable. Additionally, if k≥2k≥2, then every single entry array of order at least n≥4n≥4, where at most kk rows contain non-empty cells and where each symbol occurs in at most n−k+1n−k+1 cells, is avoidable.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 5, 6 March 2012, Pages 963–972
نویسندگان
,