An upper bound on the size of diamond-free families of sets

Grósz, Dániel and Methuku, Abhishek and Tompkins, Casey (2018) An upper bound on the size of diamond-free families of sets. JOURNAL OF COMBINATORIAL THEORY SERIES A, 156. pp. 164-194. ISSN 0097-3165

Preview

Text 1601.06332v2.pdf Download (367kB) | Preview

Abstract

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 induction method to show that View the MathML sourceLa(n,Q2)≤(2.20711+o(1))(n⌊n/2⌋), improving on the earlier bound of View the MathML source(2.25+o(1))(n⌊n/2⌋) by Kramer, Martin and Young.

Actions (login required)

Edit Item