zbMATH — the first resource for mathematics

Extending factorizations of complete uniform hypergraphs. (English) Zbl 1438.05197
Summary: We consider when a given \(r\)-factorization of the complete uniform hypergraph on \(m\) vertices \(K^h_m\) can be extended to an \(s\)-factorization of \(K^h_n\). The case of \(r = s = 1\) was first posed by P. J. Cameron [Parallelisms of complete designs. Cambridge: Cambridge University Press; London: London Mathematical Society (1976; Zbl 0333.05007)] in terms of parallelisms, and solved by R. Häggkvist and T. Hellgren [in: Combinatorics, Paul Erdős is eighty. Vol. 1. Budapest: János Bolyai Mathematical Society. 215–238 (1993; Zbl 0795.05053)]. We extend these results, which themselves can be seen as extensions of the theorem of Zs. Baranyai [in: Infinite and finite sets. To Paul Erdős on his 60th birthday. Vols. I, II, III. Amsterdam etc.: North-Holland Publishing Company. 91–108 (1975; Zbl 0306.05137)]. For \(r=s\), we show that the “obvious” necessary conditions, together with the condition that \(\operatorname{gcd}(m,n,h)=\operatorname{gcd}(n,h)\) are sufficient. In particular this gives necessary and sufficient conditions for the case where \(r=s\) and \(h\) is prime. For \(r<s\) we show that the obvious necessary conditions, augmented by \(\operatorname{gcd}(m,n,h)=\operatorname{gcd}(n,h)\), \(n\geq 2m\), and \(1\leq \frac{s}{r}\leq \frac{m}{k}[1-\binom{m-k}{h}/\binom{m}{h}]\) are sufficient, where \(k=\operatorname{gcd}(m,n,h)\). We conclude with a discussion of further necessary conditions and some open problems.
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C65 Hypergraphs
05C15 Coloring of graphs and hypergraphs
Full Text: DOI