An upper bound on the size of diamond-free families of sets

Abstract

Let $La(n,P)$ be the maximum size of a family of subsets of $[n]=\{1,2,...,n\}$ not containing $P$ as a (weak) subposet. The diamond poset, denoted $B_2$, is defined on four elements $x,y,z,w$ with the relations $x<y,z$ and $y,z<w$. $La(n,P)$ has been studied for many posets; one of the major open problems is determining $La(n,B_2)$. Studying the average number of sets from a family of subsets of $[n]$ on a maximal chain in the Boolean lattice $2^{[n]}$ has been a fruitful method. We use a partitioning of the maximal chains and introduce an induction method to show that $La(n,B_2)\le (2.20711+o(1))\left(\genfrac{}{}{0ex}{}{n}{\lfloor \frac{n}{2}\rfloor }\right)$, improving on the earlier bound of $(2.25+o(1))\left(\genfrac{}{}{0ex}{}{n}{\lfloor \frac{n}{2}\rfloor }\right)$ by Kramer, Martin and Young.

Accepted by JCTA. Writing is improved based on the suggestions of referees