Longest partial transversals in plexes

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, 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 φ*_k denote the smallest order for which there exists a k-plex that contains no transversal. We show that k≤φ_k=φ*_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 show that T(P)> max{ k(1-n^-1/2), k-n/(n-k), 5n/9-O(n/√k) }. The first of these bounds generalizes a result by Brouwer et al. and Woolbright on partial transversals in latin squares. In the special case of 3-protoplexes, we improve the lower bound for T(P) to 3n/5.