## Diamond-free Families

Series:
Combinatorics Seminar
Friday, September 17, 2010 - 15:05
1 hour (actually 50 minutes)
Location:
Skiles 255
,
Mathematics, University of South Carolina
Organizer:
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.