Embedding and Coloring Designs

Abstract

This dissertation focuses on two problems in design theory. Techniques from graph theory are frequently utilized and therefore the proofs may also be of interest to graph theorists.

The first problem focuses on completing partial latin squares with prescribed diagonals. Necessary and sufficient numerical conditions are known for the embedding of an incomplete latin square $L$ of order $n$ into a latin square $T$ of order $t \geq 2n+1$ in which each symbol is prescribed to occur in a given number of cells on the diagonal of $T$ outside of $L$. This includes the classic case where $T$ is required to be idempotent. If $t<2n$ then no such numerical sufficient conditions exist since it is known that the arrangement of symbols within the given incomplete latin square can determine the embeddability. All known examples where the arrangement is a factor share the common feature that one symbol is prescribed to appear exactly once in the diagonal of $T$ outside of $L$. We show if the prescribed diagonal contains a symbol required to appear exactly once on the diagonal of $T$ outside of $L$ and $t \leq 2n$, then there always exists a incomplete latin square satisfying the known numerical necessary conditions that is non-embeddable. Also, we solve a conjecture made over $30$ years ago stating it is only this feature that prevents numerical conditions sufficing for all $t \geq n$. Thus providing necessary and sufficient numerical conditions for the embedding of an incomplete latin square $L$ of order $n$ into a latin square $T$ of order $t$ for all $t \geq n$ in which the diagonal of $T$ outside of $L$ is prescribed in the case where no symbol is required to appear exactly once in the diagonal of $T$ outside of $L$.

The second problem focuses on (not necessarily proper) $s$-edge-colorings of $K_v$ in which, for all $u \in V(K_v)$, the edges incident with $u$ are colored using exactly $p$ colors. In the spirit of proper edge-colorings, such $(s,p)$-edge-colorings are required to be equitable: the edges at each vertex are shared evenly among $p$ colors. First, results related to the existence of equitable $(s,p)$-edge-colorings of $K_v$ and future directions related to equitable $(s,p)$-edge-colorings of $\lambda K_v$ are discussed. Then, the structure of equitable $(s,p)$-edge-colorings of $K_v$ is addressed, particularly, the number of vertices at which each color appears. Results are obtained determining how large and how small these numbers can be. Results concerning equitable $(s,p)$-$C_4$-colorings of $K_v-F$ follow as corollaries.