Toward a three-dimensional counterpart of Cruse’s theorem
Amin Bahmanian · Proceedings of the American Mathematical Society · 2023
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 m can be embedded in a symmetric latin square of order n n . Loosely speaking, this results asserts that an n n -coloring of the edges of the complete m m -vertex graph K m K_m can be embedded in a one-factorization of K n K_n if and only if n n is even and the number of edges of each color is at least m − n / 2 m-n/2 . We establish necessary and sufficient conditions under which an edge-coloring of the complete λ \lambda -fold m m -vertex 3-graph λ K m 3 \lambda K_m^3 can be embedded in a one-factorization of λ K n 3 \lambda K_n^3 . In particular, we prove the first known Ryser type theorem for hypergraphs by showing that if n ≡ 0 ( m o d 3 ) n\equiv 0\ (\mathrm {mod}\ 3) , any edge-coloring of λ <