Decomposition of regular hypergraphs

Abstract

A d-block is a 0, 1-matrix in which every row has sum d. Let Sn be the set of pairs (k, l) such that the columns of any (k + l)-block with n rows split into a k-block and an l-block. For n ≥ 5, we prove the general necessary condition that (k, l) ∈ Sn only if each element of {1, . . . , n} divides k or l. We also determine Sn for n ≤ 5. Trivially, S1 = S2 = N × N. Also S3 = {(k, l): 2 | kl}, S4 = {(k, l): 6 | kl and min{k, l} > 1}, and S5 = {(k, l): 3, 4, 5 each divide k or l, plus 11 6= min{k, l} > 7}.