کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8903178 1632404 2017 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Extremal functions of forbidden multidimensional matrices
ترجمه فارسی عنوان
توابع فوق العاده ماتریس های چند بعدی ممنوع
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We advance the extremal theory of matrices in two directions. The methods that we use come from combinatorics, probability, and analysis. Firstly, we obtain non-trivial lower and upper bounds on f(n,P,d) when n is large for every d-dimensional block permutation matrix P. We establish the tight bound Θ(nd−1) on f(n,P,d) for every d-dimensional tuple permutation matrix P. This tight bound has the lowest possible order that an extremal function of a nontrivial matrix can ever achieve. Secondly, we show that the limit inferior of the sequence {f(n,P,d)nd−1} has a lower bound 2Ω(k1∕2) for a family of k×⋯×k permutation matrices P. We also improve the upper bound on the limit superior from 2O(klogk) to 2O(k) for all k×⋯×k permutation matrices and show that the new upper bound also holds for tuple permutation matrices.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 340, Issue 12, December 2017, Pages 2769-2781
نویسندگان
, ,