2024/11/12 by Julian Galliano, Galliano, Julian, Kang, Ross J.
Computer Science · #05C35 #05D05 #06A07 #Advanced Algebra and Logic #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2411.07985
openalex publication_date 2024/11/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
For a subfamily F⊆ 2[n] of the Boolean lattice, consider the graph GF on F based on the pairwise inclusion relations among its members. Given a positive integer t, how large can F be before GF 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=2n, this question is trivial. We are interested in what happens between these two extremes. For t=2g with g=g(n) being any integer function that satisfies g(n)=o(n/log n) as 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 F be before GF must be connected?