Projects per year
Abstract
A k-plex in a latin square of order n is a selection of kn entries that includes k representatives from each row and column and k occurrences of each symbol. A 1-plex is also known as a transversal.
It is well known that if n is even then Bn, the addition table for the integers modulo n, possesses no transversals. We show that there are a great many latin squares that are similar to Bn and have no transversal. As a consequence, the number of species of transversal-free latin squares is shown to be at least nn3/2 (1/2−o(1)) for even n → ∞.
We also produce various constructions for latin squares that have no transversal but do have a k-plex for some odd k > 1. We prove a 2002 conjecture of the second author that for all even orders n > 4 there is a latin square of order n that contains a 3-plex but no transversal. We also show that for odd k and m ≥ 2, there exists a latin square of order 2km with a k-plex but no k′-plex for odd k′ < k.
| Original language | English |
|---|---|
| Article number | #P2.45 |
| Number of pages | 15 |
| Journal | The Electronic Journal of Combinatorics |
| Volume | 24 |
| Issue number | 2 |
| Publication status | Published - 30 Jun 2017 |
Keywords
- Latin square
- Plex
- Transversal
- Triplex
Projects
- 1 Finished
-
Matchings in Combinatorial Structures
Wanless, I. (Primary Chief Investigator (PCI)), Bryant, D. (Chief Investigator (CI)) & Horsley, D. (Chief Investigator (CI))
ARC - Australian Research Council, Monash University, University of Queensland , University of Melbourne
1/01/15 → 10/10/20
Project: Research
Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver