کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4655118 1632938 2015 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Forbidding intersection patterns between layers of the cube
ترجمه فارسی عنوان
ممنوع ساختن الگوهای تقاطع بین لایه های مکعب
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

A family A⊂P[n]A⊂P[n] is said to be an antichain if A⊄BA⊄B for all distinct A,B∈AA,B∈A. A classic result of Sperner shows that such families satisfy |A|≤(n⌊n/2⌋), which is easily seen to be best possible. One can view the antichain condition as a restriction on the intersection sizes between sets in different layers of P[n]P[n]. More generally one can ask, given a collection of intersection restrictions between the layers, how large can families respecting these restrictions be? Answering a question of Kalai [8], we show that for most collections of such restrictions, layered families are asymptotically largest. This extends results of Leader and the author from [11].

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 134, August 2015, Pages 103–120
نویسندگان
,