Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4655118 | Journal of Combinatorial Theory, Series A | 2015 | 18 Pages |
Abstract
A family A⊂P[n]A⊂P[n] is said to be an antichain if A⊄BA⊄B for all distinct A,B∈AA,B∈A. A classic result of Sperner shows that such families satisfy |A|≤(n⌊n/2⌋), 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 P[n]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 [8], we show that for most collections of such restrictions, layered families are asymptotically largest. This extends results of Leader and the author from [11].
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Eoin Long,