2013/07/12 by Travis Johnston, Johnston, Travis, Linyuan Lü +3 · 1 citation
Computer Science · Mathematics · #05D05 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1307.3312
openalex publication_date 2013/07/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let 2[n] denote the power set of [n]:=\1,2,..., n\. A collection \B⊂ 2[n] forms a d-dimensional \em Boolean algebra if there exist pairwise disjoint sets X0, X1,..., Xd ⊆ [n], all non-empty with perhaps the exception of X0, so that \B=X0∪ \bigcupi∈ I Xi\colon I⊆ [d]. Let b(n,d) be the maximum cardinality of a family \F⊂ 2X that does not contain a d-dimensional Boolean algebra. Gunderson, Rödl, and Sidorenko proved that b(n,d) ≤ cd n-1/2d ⋅ 2n where cd= 10d 2^-21-dd^d-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 \F with \F⊆ \tsupn is defined by hn(\F):=∑F∈ \F1/n\choose |F|. We prove the following Turán type theorem. If \F⊆ 2[n] contains no d-dimensional Boolean algebra, then hn(\F)≤ 2(n+1)^1-21-d for sufficiently large n. This results implies b(n,d) ≤ C n-1/2d ⋅ 2n, where C is an absolute constant independent of n and d. As a consequence, we improve several Ramsey-type bounds on Boolean algebras. We also prove a canonical Ramsey theorem for Boolean algebras.