Interval Packing and Covering in the Boolean Lattice

Abstract

Let 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 ⊆[ n ] : X ⊆ C ⊆ Y } where | X | = l , | Y | = u , X ⊆ Y .We study the matching number i.e. the the maximum number of pairwise disjoint edges, and the covering number i.e. the minimum number of points which cover all edges. We prove that max and that for every ε > 0 the inequalities 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