Largest component in Boolean sublattices

Abstract

For a subfamily $F\subseteq 2^{[n]}$ of the Boolean lattice, consider the graph $G_F$ on $F$ based on the pairwise inclusion relations among its members. Given a positive integer $t$, how large can $F$ be before $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)$ as $n\to \infty$, 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 $F$ be before $G_F$ must be connected?

23 pages, 2 figures; v2 includes minor corrections from review; to appear in Acta Mathematica Hungarica