You are hereHome › Hal Marcus College of Science & Engineering (CSE) › Department of Mathematics and Statistics › Kuhl, Jaromy › Longest partial transversals in plexes Style APAChicagoHarvardIEEEMLATurabian Choose the citation style. Cavenaugh, N. J., Kuhl, J., & Wanless, I. M. (2014). Longest partial transversals in plexes. Annals of Combinatorics, 18, 419-428. Longest partial transversals in plexes Details Type Academic Journal Article Title Longest partial transversals in plexes Located In Annals of Combinatorics ISSN 0218-0006 Volume 18 Start Page 419 End Page 428 Date 2014 Use/Reproduction Permission granted to the University of West Florida Libraries to digitize and/or display this item for non-profit research and educational purposes. Any reuse of this item in excess of fair use or other copyright exemptions requires the permission of the copyright holder. © Springer Basel 2014 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. Subject(s) Hypergraph matchingLatin squarePlexProtoplexTransversalRainbow matching PID uwf:25125