On diamond-free subposets of the Boolean lattice: An application of flag algebras
Date
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Journal Issue
Is Version Of
Versions
Series
Department
Abstract
The Boolean lattice of dimension two, also known as the diamond, consists of four distinct elements with the following property: A B;C D. The 3-crown consists of six distinct elements with the following property: A a subset of B, D and B a subset of C E and A a subset of C, F. A P-free family in the n-dimensional Boolean lattice is a subposet such that no collection of elements form the poset P. Note that the posets are not induced and may contain additional relations. There is a diamond-free family in the n-dimensional Boolean lattice of size (2+o(1))*( n choose n/2).
In this dissertation, we prove that any diamond-free family in the n-dimensional Boolean lattice has size at most (2:25 + o(1))
*( n choose n/2). Furthermore, we show that the so-called Lubell function of a diamond-free family in the n-dimensional Boolean lattice which contains the empty set is at most 2:25 + o(1), which is asymptotically best possible.
There is a 3-crown-free family in the n-dimensional Boolean lattice of size n choose n/2. In this dissertation, we prove that any 3-crown-free family in the n-dimensional Boolean lattice has
size at most (2(3)&half - 2)*( n choose n/2).