An upper bound on the size of diamond-free families of sets
- Grósz, Dániel
- Methuku, Abhishek
- Tompkins, Casey
DOIAbstract
Let La(n,P)La(n,P) be the maximum size of a family of subsets of [n]={1,2,…,n}[n]={1,2,…,n} not containing P as a (weak) subposet. The diamond poset, denoted Q2Q2, is defined on four elements x,y,z,wx,y,z,w with the relations x<y,zx<y,z and y,z<wy,z<w. La(n,P)La(n,P) has been studied for many posets; one of the major open problems is determining La(n,Q2)La(n,Q2). It is conjectured that View the MathML sourceLa(n,Q2)=(2+o(1))(n⌊n/2⌋), and infinitely many significantly different, asymptotically tight constructions are known. Studying the average number of sets from a family of subsets of [n][n] on a maximal chain in the Boolean lattice 2[n]2[n] has been a fruitful method. We use a partitioning of the maximal chains and introduce an induc...
Add to ORKG