Covering Complete Hypergraphs with Cuts of Minimum Total Size

A cut X, V − X] in a hypergraph with vertex-set V is the set of all edges that meet both X and V − X. Let s _r (n) denote the minimum total size of any cover of the edges of the complete r-uniform hypergraph on n vertices K_n^r{K_n^r} by cuts. We show that there is a number n _r such that for every n > n _r , s _r (n) is uniquely achieved by a cover with ?\fracn-1r-1?{\lfloor \frac{n-1}{r-1}\rfloor} cuts X _i , V − X _i ] such that the X _i are pairwise disjoint sets of size at most r − 1. We show that c₁r2^r < n_r < c₂r⁵2^r{c_1r2^r < n_r < c_2r^52^r} for some positive absolute constants c ₁ and c ₂. Using known results for s ₂(n) we also determine s ₃(n) exactly for all n.