کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4655139 | 1632936 | 2015 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Boolean algebras and Lubell functions Boolean algebras and Lubell functions](/preview/png/4655139.png)
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.
Journal: Journal of Combinatorial Theory, Series A - Volume 136, November 2015, Pages 174–183