×

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.
MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C65 Hypergraphs
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI