Metrics
164 Record Views
Journal article
Longest partial transversals in plexes
Annals of Combinatorics, Vol.18, pp.419-428
18
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.
Related links
Details
- Title
- Longest partial transversals in plexes
- Publication Details
- Annals of Combinatorics, Vol.18, pp.419-428
- Resource Type
- Journal article
- Publisher
- Birkhaeuser Science; Switzerland
- Series
- 18
- Copyright
- © Springer Basel 2014
- Identifiers
- 99380090767406600
- Academic Unit
- Mathematics and Statistics; Hal Marcus College of Science and Engineering
- Language
- English