IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

On diamond-free subposets of the Boolean lattice

  • March 16, 2012
  • 3:30 p.m.
  • LeConte 312

Abstract

The Boolean lattice is the partially ordered set (poset) that consists of the subsets of a finite set, ordered by inclusion. The Boolean lattice of dimension n is the one in which the underlying set has cardinality n. A subposet of a Boolean lattice is said to be diamond-free if it does not contain 4 subsets A, B, C, and D with the properties that

(a) A is properly included in B and B is properly included in D, and
(b) A is properly included in C and C is properly include in D, and
(c) The sets B and C could be unrelated.

A basic construction gives a diamond-free poset in the n-dimensional Boolean lattice that is of size $(2-o(1)){\binom{n}{\lfloor n/2\rfloor}}$. Griggs, Li and Lu proved that all such posets have size at most $(2+3/11+o(1)){\binom{n}{\lfloor n/2\rfloor}}$. In this talk, we show that diamond-free posets in the n-dimensional Boolean lattice have size at most $(2.25-o(1)){\binom{n}{\lfloor n/2\rfloor}}$. Our proof uses the method of flag algebras due to Razborov. However, the explanation of the proof does not require knowing the general flag algebra method.

This is joint work with Lucas Kramer and Michael Young, both of Iowa State University.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC