×

zbMATH — the first resource for mathematics

Extending edge-colorings of complete hypergraphs into regular colorings. (English) Zbl 07047770
Summary: Let \(\begin{pmatrix}X\\h\end{pmatrix}\) be the collection of all \(h\)-subsets of an \(n\)-set \(X\supseteq Y\). Given a coloring (partition) of a set \(s\subseteq\begin{pmatrix}X\\h\end{pmatrix}\), we are interested in finding conditions under which this coloring is extendible to a coloring of \(\begin{pmatrix}X\\h\end{pmatrix}\) so that the number of times each element of \(X\) appears in each color class (all sets of the same color) is the same number \(r\). The case \(S=\varnothing, r=1\) was studied by Sylvester in the 18th century and remained open until the 1970s. The case \(h=2, r=1\) is extensively studied in the literature and is closely related to completing partial symmetric Latin squares. For \(s=\begin{pmatrix}Y\\h\end{pmatrix}\), we settle the cases \(h=4, \vert X\vert\geq 4.847323\vert Y\vert\), and \(h=5, \vert X\vert\geq 6.285214\vert Y\vert\) completely. Moreover, we make partial progress toward solving the case where \(s=\begin{pmatrix}X\\h\end{pmatrix}\backslash\begin{pmatrix}Y\\h\end{pmatrix}\). These results can be seen as extensions of the famous Baranyai’s theorem, and make progress toward settling a 40-year-old problem posed by Cameron.
MSC:
05C Graph theory
PDF BibTeX XML Cite
Full Text: DOI