Extending edge-colorings of complete hypergraphs into regular colorings

Abstract: Let

be the collection of all

h

-subsets of an

n

-set

X s u p s e t e q Y

. Given a coloring (partition) of a set

, we are interested in finding conditions under which this coloring is extendible to a coloring of

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 = v a r n o t h i n g, 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

, we settle the cases

h = 4, | X | g e q 4.847323 | Y |

, and

h = 5, | X | g e q 6.285214 | Y |

completely. Moreover, we make partial progress toward solving the case where

. 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.

Recommendations

Cited in

(5)

This page was built for publication: Extending edge-colorings of complete hypergraphs into regular colorings