Series:

Combinatorics Seminar

Friday, September 17, 2010 - 15:05

1 hour (actually 50 minutes)

Location:

Skiles 255

Speaker:

Jerry Griggs, Carolina Distinguished Professor and Chair

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.