Among graphs, groups, and latin squares

Date created: 
Latin square (05B15)
Group-labelled graphs (05C25)
Hamilton cycles (05C45)
Partial transversal
Harmonious group

A latin square of order n is an n × n array in which each row and each column contains each of the numbers {1, 2, . . . , n}. A k-plex in a latin square is a collection of entries which intersects each row and column k times and contains k copies of each symbol. This thesis studies the existence of k-plexes and approximations of k-plexes in latin squares, paying particular attention to latin squares which correspond to multiplication tables of groups. The most commonly studied class of k-plex is the 1-plex, better known as a transversal. Although many latin squares do not have transversals, Brualdi conjectured that every latin square has a near transversal—i.e. a collection of entries with distinct symbols which in- tersects all but one row and all but one column. Our first main result confirms Brualdi’s conjecture in the special case of group-based latin squares. Then, using a well-known equivalence between edge-colorings of complete bipartite graphs and latin squares, we introduce Hamilton 2-plexes. We conjecture that every latin square of order n ≥ 5 has a Hamilton 2-plex and provide a range of evidence for this conjecture. In particular, we confirm our conjecture computationally for n ≤ 8 and show that a suitable analogue of Hamilton 2-plexes always occur in n × n arrays with no symbol appearing more than n/√96 times. To study Hamilton 2-plexes in group-based latin squares, we generalize the notion of harmonious groups to what we call H2-harmonious groups. Our second main result classifies all H2-harmonious abelian groups. The last part of the thesis formalizes an idea which first appeared in a paper of Cameron and Wanless: a (k,l)-plex is a collection of entries which intersects each row and column k times and contains at most l copies of each symbol. We demonstrate the existence of (k, 4k)-plexes in all latin squares and (k, k + 1)-plexes in sufficiently large latin squares. We also find analogues of these theorems for Hamilton 2-plexes, including our third main result: every sufficiently large latin square has a Hamilton (2,3)-plex.

Document type: 
This thesis may be printed or downloaded for non-commercial research and scholarly purposes. Copyright remains with the author.
Luis Goddyn
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.