Forbidding intersection patterns between layers of the cube

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

Abstract

A family ${\cal A}$ is said to be an antichain if $A \not \subset B$ for all distinct $A, B \in {\cal A}$. A classic result of Sperner shows that such families satisfy $|{\cal A}| \leq \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 ${\cal 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].

Details

Original languageEnglish
Pages (from-to)103-120
Number of pages18
JournalJournal of Combinatorial Theory, Series A
Volume134
Publication statusPublished - 1 Aug 2015