کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4655139 1632936 2015 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Boolean algebras and Lubell functions
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Boolean algebras and Lubell functions
چکیده انگلیسی

Let 2[n]2[n] denote the power set of [n][n], where [n]={1,2,…,n}[n]={1,2,…,n}. A collection B⊂2[n]B⊂2[n] forms a d-dimensional Boolean algebra   if there exist pairwise disjoint sets X0,X1,…,Xd⊆[n]X0,X1,…,Xd⊆[n], all non-empty with perhaps the exception of X0X0, so that B={X0∪⋃i∈IXi:I⊆[d]}B={X0∪⋃i∈IXi:I⊆[d]}. Let b(n,d)b(n,d) be the maximum cardinality of a family F⊂2XF⊂2X that does not contain a d  -dimensional Boolean algebra. Gunderson, Rödl, and Sidorenko proved that b(n,d)≤cdn−1/2d⋅2nb(n,d)≤cdn−1/2d⋅2n where cd=10d2−21−ddd−2−dcd=10d2−21−ddd−2−d.In this paper, we use the Lubell function as a new measurement for large families instead of cardinality. The Lubell value of a family of sets FF with F⊆2[n]F⊆2[n] is defined by hn(F)=∑F∈F1/(n|F|). We prove the following Turán type theorem. If F⊆2[n]F⊆2[n] contains no d  -dimensional Boolean algebra, then hn(F)≤2(n+1)1−21−dhn(F)≤2(n+1)1−21−d for sufficiently large n  . This result implies b(n,d)≤Cn−1/2d⋅2nb(n,d)≤Cn−1/2d⋅2n, where C is an absolute constant independent of n and d  . With some modification, the ideas in Gunderson, Rödl, and Sidorenko's proof can be used to obtain this result. We apply the new bound on b(n,d)b(n,d) to improve several Ramsey-type bounds on Boolean algebras. We also prove a canonical Ramsey theorem for Boolean algebras.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 136, November 2015, Pages 174–183
نویسندگان
, , ,