Detachments of Hypergraphs I: The Berge–Johnson Problem

Source abstract

A detachment of a hypergraph is formed by splitting each vertex into one or more subvertices, and sharing the incident edges arbitrarily among the subvertices. For a given edge-coloured hypergraph , we prove that there exists a detachment such that the degree of each vertex and the multiplicity of each edge in (and each colour class of ) are shared fairly among the subvertices in (and each colour class of , respectively). Let $(\lambda_1,\ldots,\lambda_m) K^{h_1,\ldots,\, h_m}_{p_1,\ldots,\, p_n}$ be a hypergraph with vertex partition { V 1 ,. . ., V n }, | V i | = p i for 1 ≤ i ≤ n such that there are λ i edges of size h i incident with every h i vertices, at most one vertex from each part for 1 ≤ i ≤ m (so no edge is incident with more than one vertex of a part). We use our detachment theorem to show that the obvious necessary conditions for $(\lambda_1\dots,\lambda_m) K^{h_1,\ldots,h_m}_{p_1,\ldots,p_n}$ to be expressed as the union 1 ∪ ··· ∪ k of k edge-disjoint factors, where for 1 ≤ i ≤ k , i is r i -regular, are also sufficient. Baranyai solved the case of h 1 = ··· = h m , λ 1 = ··· = λ m = 1, p 1 = ··· = p m , r 1 = ··· = r k . Berge and Johnson (and later Brouwer and Tijdeman, respectively) considered (and solved, respectively) the case of h i = i , 1 ≤ i ≤ m , p 1 = ··· = p m = λ 1 = ··· = λ m = r 1 = ··· = r k = 1. We also extend our result to the case where each i is almost regular.