Article ID Journal Published Year Pages File Type
4655118 Journal of Combinatorial Theory, Series A 2015 18 Pages PDF
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
,