Diamond-free Families

Combinatorics Seminar
Friday, September 17, 2010 - 3:05pm
1 hour (actually 50 minutes)
Skiles 255
Mathematics, University of South Carolina
Given a finite poset $P$, we consider the largest size ${\rm La}(n,P)$ of a family of subsets of $[n]:=\{1,\ldots,n\}$ that contains no  subposet $HP.  Sperner's Theorem (1928) gives that ${\rm La}(n,P_2)= {n\choose{\lfloor n/2\rfloor}}$,  where $P_2$ is the two-element chain.    This problem has been studied intensively in recent years, and it is conjectured that $\pi(P):=  \lim_{n\rightarrow\infty} {\rm La}(n,P)/{n\choose{\lfloor n/2\rfloor}}$  exists for general posets $P$, and, moreover, it is an integer. For $k\ge2$ let $D_k$ denote the $k$-diamond poset $\{A< B_1,\ldots,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  $\pi(D_k)$ for infinitely many values $k$.  A stubborn open problem is to show that $\pi(D_2)=2$; here we prove $\pi(D_2)<2.273$ (if it exists).    This is joint work with Wei-Tian Li and Linyuan Lu of University of South Carolina.