کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5772924 | 1631058 | 2018 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Constructing (0,1)-matrices with large minimal defining sets
ترجمه فارسی عنوان
ساخت (0.1) -مقدمات با مجموعه های کمینه تعریف کمینه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
اعداد جبر و تئوری
چکیده انگلیسی
If D is a partially filled-in (0,1)-matrix with a unique completion to a (0,1)-matrix M (with prescribed row and column sums), we say that D is a defining set for M. Let A2m,m be the set of (0,1)-matrices of dimensions 2mÃ2m with uniform row and column sum m. It is shown in Cavenagh (2013) [3] that the smallest possible size for a defining set of an element of A2m,m is precisely m2. In this note when m is a power of two we construct an element of A2m,m which has no defining set of size less than 2m2âo(m2). Given that it is easy to show any A2m,m has a defining set of size at most 2m2, this construction is asymptotically optimal. Our construction is based on a array, defined using linear algebra, in which any subarray has asymptotically the same number of 0's and 1's.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Linear Algebra and its Applications - Volume 537, 15 January 2018, Pages 38-47
Journal: Linear Algebra and its Applications - Volume 537, 15 January 2018, Pages 38-47
نویسندگان
Nicholas J. Cavenagh, Reshma Ramadurai,