pith. sign in

arxiv: 1601.06332 · v2 · pith:7LA5FBMRnew · submitted 2016-01-24 · 🧮 math.CO

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

classification 🧮 math.CO
keywords beenbinomboundfamilyfracleftlfloormaximal
0
0 comments X
read the original abstract

Let $La(n,P)$ be the maximum size of a family of subsets of $[n]=\{1,2,...,n\}$ not containing $P$ as a (weak) subposet. The diamond poset, denoted $B_{2}$, is defined on four elements $x,y,z,w$ with the relations $x<y,z$ and $y,z<w$. $La(n,P)$ has been studied for many posets; one of the major open problems is determining $La(n,B_{2})$. Studying the average number of sets from a family of subsets of $[n]$ on a maximal chain in the Boolean lattice $2^{[n]}$ has been a fruitful method. We use a partitioning of the maximal chains and introduce an induction method to show that $La(n,B_{2})\leq(2.20711+o(1))\binom{n}{\left\lfloor \frac{n}{2}\right\rfloor }$, improving on the earlier bound of $(2.25+o(1))\binom{n}{\left\lfloor \frac{n}{2}\right\rfloor }$ by Kramer, Martin and Young.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.