2013/11/22 by Eoin Long, Long, Eoin
Mathematics · #05D05 #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Mathematical Dynamics and Fractals
paper · pdf · doi:10.48550/arxiv.1311.5713
openalex publication_date 2013/11/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A family \mathcal A ⊂ \mathcal P [n] is said to be an antichain if A \not ⊂ B for all distinct A,B ∈ \mathcal A. A classic result of Sperner shows that such families satisfy |\mathcal A| ≤ \binom n\lfloor n/2\rfloor, which is easily seen to be best possible. One can view the antichain condition as a restriction on the intersection sizes between sets in different layers of \mathcal P [n]. More generally one can ask, given a collection of intersection restrictions between the layers, how large can families respecting these restrictions be? Answering a question of Kalai, we show that for most collections of such restrictions, layered families are asymptotically largest. This extends results of Leader and the author.