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
Full Text: