Extending Edge-colorings of Complete Hypergraphs into Regular Colorings
share
Let Xh be the collection of all h-subsets of an n-set X⊇ Y. Given a coloring (partition) of a set S⊆Xh, we are interested in finding conditions under which this coloring is extendible to a coloring of Xh 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=∅, 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=Yh, we settle the cases h=4, |X|≥ 4.847323|Y|, and h=5, |X|≥ 6.285214|Y| completely. Moreover, we make partial progress toward solving the case where S=Xh\Yh. 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.
READ FULL TEXT