Sharp Embeddings of Layer-Rainbow Cubes and Orthogonal Pairs

Abstract

We determine the exact extension threshold for one-factorizations of complete tripartite $3$-uniform hypergraphs. Equivalently, for $n>m$, every order-$m$ layer-rainbow cube embeds in one of order $n$ if and only if $n\ge 2m$. We then study injectively orthogonal pairs, in which no ordered pair of symbols is repeated. Such pairs exist in every positive order except $2$, and every order-$m$ pair with $m\ge 3$ embeds in every order $n\ge 3m$. At the sharp order $2m$, embedding occurs exactly when the pair has a disjoint mate. The symbol-pair graph carries three distinguished one-factorizations whose triple intersections recover the cube, yielding several sufficient conditions for sharp embedding, including a finite-group construction. Finally, layer-rainbow cubes are proper $n^2$-colorings of the square of the Hamming graph, and the three one-factorizations of an orthogonal pair recover the Hamming geometry of the cells.

arXiv comment13 pages