Diamond-free Families

Series
Combinatorics Seminar
Time
Friday, September 17, 2010 - 3:05pm for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Jerry Griggs, Carolina Distinguished Professor and Chair – Mathematics, University of South Carolina
Organizer
Prasad Tetali
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 HP.SpernersTheorem(1928)givesthat{\rm La}(n,P_2)= {n\choose{\lfloor n/2\rfloor}},whereP_2isthetwoelementchain.Thisproblemhasbeenstudiedintensivelyinrecentyears,anditisconjecturedthat\pi(P):=  \lim_{n\rightarrow\infty} {\rm La}(n,P)/{n\choose{\lfloor n/2\rfloor}}existsforgeneralposetsP,and,moreover,itisaninteger.Fork\ge2letD_kdenotethekdiamondposet\{A< B_1,\ldots,B_k < C\}.WestudytheaveragenumberoftimesarandomfullchainmeetsaPfreefamily,calledtheLubellfunction,anduseitforP=D_ktodetermine\pi(D_k)forinfinitelymanyvaluesk.Astubbornopenproblemistoshowthat\pi(D_2)=2;hereweprove\pi(D_2)<2.273$ (if it exists).    This is joint work with Wei-Tian Li and Linyuan Lu of University of South Carolina.