• Speaker: Dr Thomas Kalinowski, CARMA, The University of Newcastle
  • Title: Maximal antichains on two levels of the Boolean lattice
  • Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
  • Time and Date: 4:00 pm, Thu, 28th Oct 2010
  • Abstract:

    We are looking at families of finite sets, more specifically subsets of [n]={1,2,...,n}. In particular, we are interested in antichains, that means no member of the family is contained in another one. In this talk we focus on antichains containing only sets of two different cardinalities, say k and l, and study the question what the smallest size of a maximal antichain is (maximal in the sense that it is impossible to add any k-set or l-set without violating the antichain property). This can be nicely reformulated as a problem in extremal (hyper)graph theory, looking similar to the TurĂ¡n problem on the maximum number of edges in a graph without a complete subgraphs on l vertices. We sketch the solution for the case (k,l)=(2,3), conjecture an optimal construction for the case (k,l)=(2,4) and present some asymptotic bounds for this case.

  • [Permanent link]