Completion of partial latin squares

Self-archived: 17 October 2009

This page hosts my self-archived version of my honours thesis:

I have not updated this thesis since I submitted it, and so I apologise in advance for both the writing style and the typesetting—I dearly hope my skills in both areas have improved since then.

The main reason for posting this thesis online is because it gets cited occasionally, and so it seems only fair to make it available. To save readers the trouble of hunting through 80 pages, the parts you are probably looking for are:

• Lemma 4.3.14, which shows that any k-plex of order n >= 4k can be extended to a (k+1)-plex of order n, with significant freedom as to how this (k+1)-plex is constructed;
• Conjecture 4.3.15, which proposes that every k-plex of order n >= 4k has a completion.

Note that throughout this thesis I refer to a k-plex as a k-stagger (the term k-plex, whilst certainly more sensible, did not exist at the time).