| Abstrakt: |
Completing partial latin squares is NP-complete. Motivated by Ryser's theorem for latin rectangles, in 1974, Cruse found conditions that ensure a partial symmetric latin square of order m can be embedded in a symmetric latin square of order n. Loosely speaking, this results asserts that an n-coloring of the edges of the complete m-vertex graph K_m can be embedded in a one-factorization of K_n if and only if n is even and the number of edges of each color is at least m-n/2. We establish necessary and sufficient conditions under which an edge-coloring of the complete \lambda-fold m-vertex 3-graph \lambda K_m^3 can be embedded in a one-factorization of \lambda K_n^3. In particular, we prove the first known Ryser type theorem for hypergraphs by showing that if n\equiv 0\ (\mathrm {mod}\ 3), any edge-coloring of \lambda K_m^3 where the number of triples of each color is at least m/2-n/6, can be embedded in a one-factorization of \lambda K_n^3. Finally we prove an Evans type result by showing that if n\equiv 0\ (\mathrm {mod}\ 3) and n\geq 3m, then any q-coloring of the edges of any F\subseteq \lambda K_m^3 can be embedded in a one-factorization of \lambda K_n^3 as long as q\leq \lambda \binom {n-1}{2}-\lambda \binom {m}{3}/\left \lfloor m/3\right \rfloor. [ABSTRACT FROM AUTHOR] |
