Combinatorics, Probability and Computing

Table of Contents - 1996 - Volume 5, Issue 04  

Research Article

Interval Packing and Covering in the Boolean Lattice

Konrad Engela1

a1 Universität Rostock, FB Mathematik, 18051 Rostock, Germany

Abstract

Let S0963548300002121inline1 be the hypergraph whose points are the subsets X of [n] := {1,…,n} with l≤ |X| ≤ u, l < u, and whose edges are intervals in the Boolean lattice of the form I = {C xs2286[n] : Xxs2286Cxs2286Y} where |X| = l, |Y| = u, X xs2286 Y.We study the matching number S0963548300002121inline2 i.e. the the maximum number of pairwise disjoint edges, and the covering number S0963548300002121inline3 i.e. the minimum number of points which cover all edges. We prove that max S0963548300002121inline4 and that for every ε > 0 the inequalities S0963548300002121inline5 hold, where for the lower bounds we suppose that n is not too small. The corresponding fractional numbers can be determined exactly. Moreover, we show by construction that S0963548300002121inline6

(Received September 29 1994)

(Revised April 07 1995)