On diamond-free subposets of the Boolean lattice

Abstract

The Boolean lattice of dimension two, also known as the diamond, consists of four distinct elements with the following property: $A\subset B,C\subset D$. A diamond-free family in the $n$-dimensional Boolean lattice is a subposet such that no four elements form a diamond. Note that elements $B$ and $C$ may or may not be related. There is a diamond-free family in the $n$-dimensional Boolean lattice of size $(2-o(1))\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$. In this paper, we prove that any diamond-free family in the $n$-dimensional Boolean lattice has size at most $(2.25+o(1))\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$. Furthermore, we show that the so-called Lubell function of a diamond-free family in the $n$-dimensional Boolean lattice is at most $2.25+o(1)$, which is asymptotically best possible.

23 pages, 10 figures Accepted to Journal of Combinatorial Theory, Series A

References in corpus (1)

• Largest family without A union B contained in C intersect D

Cited by in corpus (11)

• Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
• Lubell mass and induced partially ordered sets
• Set families with forbidden subposets
• A new bound for the 2/3 conjecture
• The Boolean Rainbow Ramsey Number of Antichains, Boolean Posets, and Chains
• On crown-free families of subsets
• Poset-free Families and Lubell-boundedness
• The Asymptotic Bound of the Lubell Function for Diamond-free Families
• Families of Subsets Without a Given Poset in the Interval Chains
• Packing Posets in the Boolean Lattice
• An improved bound on the diamond-free poset problem