Logo image
Back
Longest partial transversals in plexes
Journal article   Peer reviewed

Longest partial transversals in plexes

Nichaloas J. Cavenaugh, Jaromy Kuhl and Ian M. Wanless
Annals of Combinatorics, Vol.18, pp.419-428
18
2014

Metrics

165 Record Views

Abstract

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.

Details

Logo image