Detachments of Hypergraphs I: The Berge-Johnson Problem

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-colored hypergraph $\scr F$, we prove that there exists a detachment $\scr G$ such that the degree of each vertex and the multiplicity of each edge in $\scr F$ (and each color class of $\scr F$) are shared fairly among the subvertices in $\scr G$ (and each color class of $\scr G$, respectively). Let $({\lambda }_1\dots ,{\lambda }_m)K_{p_1,\dots ,p_n}^{h_1,\dots ,h_m}$ be a hypergraph with vertex partition $\{V_1,\dots ,V_n\}$, $|V_i|=p_i$ for $1\le i\le n$ such that there are ${\lambda }_i$ edges of size $h_i$ incident with every $h_i$ vertices, at most one vertex from each part for $1\le i\le 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_{p_1,\dots ,p_n}^{h_1,\dots ,h_m}$ to be expressed as the union $\scr G_1\cup \ldots \cup\scr G_k$ of $k$ edge-disjoint factors, where for $1\le i\le k$, $\scr G_i$ is $r_i$-regular, are also sufficient. Baranyai solved the case of $h_1=\cdots =h_m$, ${\lambda }_1=\dots ,{\lambda }_m=1$, $p_1=\cdots =p_m$, $r_1=\cdots =r_k$. Berge and Johnson, (and later Brouwer and Tijdeman, respectively) considered (and solved, respectively) the case of $h_i=i$, $1\le i\le m$, $p_1=\cdots =p_m={\lambda }_1=\cdots ={\lambda }_m=r_1=\cdots =r_k=1$. We also extend our result to the case where each $\scr G_i$ is almost regular.

11 pages, 1 figure

References in corpus (1)

• Multiply Balanced Edge Colorings of Multigraphs

Cited by in corpus (4)

• Disjoint spread systems and fault location
• Embedding factorizations for 3-uniform hypergraphs
• Extending Edge-colorings of Complete Hypergraphs into Regular Colorings
• Factorizations of Complete Multipartite Hypergraphs