# 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.