کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4655259 1632944 2014 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An extremal problem on crossing vectors
ترجمه فارسی عنوان
یک مشکل افراطی در عبور از بردارها
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

For positive integers w and k, two vectors A and B   from ZwZw are called k-crossing if there are two coordinates i and j   such that A[i]−B[i]≥kA[i]−B[i]≥k and B[j]−A[j]≥kB[j]−A[j]≥k. What is the maximum size of a family of pairwise 1-crossing and pairwise non-k  -crossing vectors in ZwZw? We state a conjecture that the answer is kw−1kw−1. We prove the conjecture for w≤3w≤3 and provide weaker upper bounds for w≥4w≥4. Also, for all k and w  , we construct several quite different examples of families of desired size kw−1kw−1. This research is motivated by a natural question concerning the width of the lattice of maximum antichains of a partially ordered set.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 128, November 2014, Pages 41–55
نویسندگان
, , , , ,