Dr. Jaromy S Kuhl

In 2003 Grüttmüller proved that if n ⩾ 3 is odd, then a partial transversal of the Cayley table of ℤₙ with length 2 is completable to a transversal. Additionally, he conjectured that a partial transversal of the Cayley table of ℤₙ with length k is completable to a transversal if and only if n is odd and either n ∈ {k, k + 1} or n ⩾ 3k - 1. Cavenagh, Hämäläinen, and Nelson (in 2009) showed the conjecture is true when k = 3 and n is prime. In this paper, we prove Grüttmüller's conjecture for k = 2 and k = 3 by establishing a more general result for Cayley tables of Abelian groups of odd order.

Let a, b, c, d, and e be positive integers. In 1982 Heinrich showed the existence of a partitioned incomplete Latin square (PILS) of type (a, b, c) and (a, b, c, d) if and only if a = b = c and 2a ≥ d. For PILS of type (a, b, c, d, e) with a ≤ b ≤ c ≤ d ≤ e, it is necessary that a+b+c ≥ e, but
not sufficient. In this paper we prove an additional necessary condition and classify the existence of PILS of type (a, b, c, d, a + b + c) and PILS with three equal parts. Lastly, we show the existence of a family of PILS in which the parts are nearly the same size.

Let n₁,..., nₖ ∈ ℤ⁺ and n₁+...+nₖ =n The integer partition (n₁,..., nₖ) is said to be realized if there is a latin square of order n with pairwise disjoint subsquares of order n for each 1 ≤i ≤ k. In this paper, we construct latin squares realizing partitions of the form (aˢ, bᵗ); that is, partitions
with s parts of size a and t parts of size b, where a < b. Heinrich (1982) showed that (1) if s ≥ 3 and t ≥ 3, then there is a latin square realizing (aˢ, bᵗ), (2) (aˢ, b) is realized if and only if (s−1)a ≥ b, and (3) (a, bᵗ) is realized if and only if t ≥ 3. In this paper, we resolve the open
cases. We show that (a², bᵗ) is realized if and only if t ≥ 3 and (aˢ, b²) is realized if and only if as ≥ b.

In this paper we give an alternate proof that it is always possible to complete partial Latin squares with two filled rows and two filled columns, except for a few small counterexamples. The proof here is significantly shorter than the most recent proof by Adams, Bryant, and Buchanan. Additionally, we find sufficient conditions under which a partial Latin square with two filled rows and at least three filled columns can be completed.

A proper coloring of a Latin square of order n is an assignment of colors to its elements triples such that each row, column and symbol is assigned n distinct colors. Equivalently, a proper coloring of a Latin square is a partition into partial transversals. The chromatic index of a Latin square is the least number of colors needed for a proper coloring. We study the chromatic index of the cyclic Latin square which arises from the addition table for the integers modulo n. We obtain the best possible bounds except for the case when n=2 is odd and divisible
by 3. We make some conjectures about the chromatic index, suggesting a generalization of Ryser's conjecture (that every Latin square of odd order contains a transversal).

In this paper we develop two methods for completing partial latin squares and prove the following. Let be a partial latin square of order in which all non-empty cells occur in at most squares. If are positive integers for which and if is the union of subsquares each with order , then can be completed. We additionally show that if and is the union of identical squares with disjoint rows and columns, then can be completed. For smaller values of we show that a completion does not always exist.

A k-protoplex of order n is a partial latin square of order n such that each row and column contains precisely k entries and each symbol occurs precisely k times. If a k-protoplex is completable to a latin square, then it is a k-plex. A 1-protoplex is a transversal. Let φk denote
the smallest order for which there exists a k-protoplex that contains no transversal, and let φₖ* denote the smallest order for which there exists a k-plex that contains no transversal. We show that k ⩽ φₖ =φₖ∗ ⩽ k+1 for all k ⩾ 6. Given a k-protoplex P of order n, we define T(P) to be the size of the largest partial transversal in P. We explore upper and lower bounds for T(P). Aharoni et al. have conjectured that T(P) ⩾ (k−1)n/k. We find that
T(P) > max {k(1−n⁻¹/²), k−n/(n−k), n−O(nk⁻¹/² log³/²k)}.
In the special case of 3-protoplexes, we improve the lower bound for T(P) to 3n/5.

It is well known that all n×n partial Latin squares with at most n−1 entries are completable. Our intent is to extend this well known statement to partial Latin cubes. We show that if an n×n×n partial Latin cube contains at most n − 1 entries, no two of which occupy the same row, then the partial Latin cube is completable. Also included in this paper is the problem of completing 2×n×n partial Latin boxes with at most n − 1 entries. Given certain sufficient conditions, we show when such partial Latin boxes are completable and then extendable to a deeper Latin box.

In this paper, we combine the notions of completing and avoiding partial latin squares. Let P be a partial latin square of order n and let 𝑄 be the set of partial latin squares of order n that avoid P. We say that P is Q-completable if P can be completed to a latin square that
avoids Q ∈ 𝑄. We prove that if P has order 4t and contains at most t − 1 entries, then P is Q-completable for each Q ∈ 𝑄 when t ≥ 9.

In 2000 Cho, Kim and Nam proved that P(n), the path on n vertices, is a 2-step competition graph for all n. In 2005, Helleloid proved that P(n) is an (n - 1)- and (n - 2)-step competition graph for all n and proved further that of all connected triangle-free graphs on n vertices, only the star is an m-step competition graph for m >= n. In this paper we show that if m divides n - 1 or n - 2, then P(n) is an m-step competition graph and that if n >= 6 and n/2 <= m <= n - 3, then P(n) is not an m-step competition graph. (C) 2010 Elsevier B.V. All rights reserved.