Connected Baranyai's Theorem

Abstract

Let $K_n^h=(V,(\genfrac{}{}{0ex}{}{V}{h}))$ be the complete $h$-uniform hypergraph on vertex set $V$ with $|V|=n$. Baranyai showed that $K_n^h$ can be expressed as the union of edge-disjoint $r$-regular factors if and only if $h$ divides $rn$ and $r$ divides $\left(\genfrac{}{}{0ex}{}{n-1}{h-1}\right)$. Using a new proof technique, in this paper we prove that $\lambda K_n^h$ can be expressed as the union ${\mathcal{G}}_1\cup \dots \cup {\mathcal{G}}_k$ of $k$ edge-disjoint factors, where for $1\le i\le k$, ${\mathcal{G}}_i$ is $r_i$-regular, if and only if (i) $h$ divides $r_{i}n$ for $1\le i\le k$, and (ii) ${\sum }_{i=1}^k{r}_i=\lambda \left(\genfrac{}{}{0ex}{}{n-1}{h-1}\right)$. Moreover, for any $i$ ($1\le i\le k$) for which $r_i\ge 2$, this new technique allows us to guarantee that ${\mathcal{G}}_i$ is connected, generalizing Baranyai's theorem, and answering a question by Katona.

7 pages, 2 figures

References in corpus (5)

• Multiply Balanced Edge Colorings of Multigraphs
• Detachments of Hypergraphs I: The Berge-Johnson Problem
• Embedding factorizations for 3-uniform hypergraphs
• Detachments of Amalgamated 3-uniform Hypergraphs : Factorization Consequences
• Embedding an Edge-colored $K(a^{(p)};\lambda ,\mu )$ into a Hamiltonian Decomposition of $K(a^{(p+r)};\lambda ,\mu )$

Cited by in corpus (3)

• Partitioning The Edge Set of a Hypergraph Into Almost Regular Cycles
• Factorizations of Complete Multipartite Hypergraphs
• Connected Fair Detachments of Hypergraphs I