Diamond-free Families

Abstract

Given a finite poset P, we consider the largest size La(n,P) of a family of subsets of $[n]:=\{1,...,n\}$ that contains no subposet P. This problem has been studied intensively in recent years, and it is conjectured that $\pi (P):={\lim }_{n\to \infty }La(n,P)/nchoosen/2$ exists for general posets P, and, moreover, it is an integer. For $k\ge 2$ let $\D_k$ denote the $k$-diamond poset $\{A<B_1,...,B_k<C\}$. We study the average number of times a random full chain meets a $P$-free family, called the Lubell function, and use it for $P=\D_k$ to determine $π(\D_k)$ for infinitely many values $k$. A stubborn open problem is to show that $π(\D_2)=2$; here we make progress by proving $π(\D_2)\le 2 3/11$ (if it exists).

16 pages