Acta Mathematica Hungarica Математика (общая)
Largest component in Boolean sublattices
Аннотация
Abstract For a subfamily $$\mathcal{F}\subseteq 2^{[n]}$$ F ⊆ 2 [ n ] of the Boolean lattice, consider the graph $$G_\mathcal{F}$$ G F on $$\mathcal{F}$$ F based on the pairwise inclusion relations among its members. Given a positive integer t , how large can $$\mathcal{F}$$ F be before $$G_\mathcal{F}$$ G F must contain some component of order greater than t ? For t = 1, this question was answered exactly almost a century ago by Sperner: the size of a middle layer of the Boolean lattice. For t = 2 n , this question is trivial. We are interested in what happens between these two extremes. For t = 2 g with g = g ( n ) being any integer function that satisfies $$g(n)=o(n/\log n)$$ g ( n ) = o ( n / log n ) as $$n\to\infty$$ n → ∞ , we give an asymptotically sharp answer to the above question: not much larger than the size of a middle layer. This constitutes a nontrivial generalisation of Sperner's theorem. We do so by a reduction to a Turán-type problem for rainbow cycles in properly edge-coloured graphs. Among other results, we also give a sharp answer to the question, how large can $$\mathcal{F}$$ F be before $$G_\mathcal{F}$$ G F must be connected?