A Generalisation of the Moore-MacNeish Construction of MOLS for SOMAs

In this webpage, we discuss some results from Chapter 3 (page 57) of my PhD thesis. In particular, we discuss the implication of these results for the functions M(n) and N(n) for SOMAs. We recall that the definitions of these functions are given here.

Construction 3.2.1 (page 58) of my PhD thesis is a known construction of MOLS called the Moore-MacNeish Construction of MOLS. Chapter 3 of my PhD thesis is on a generalisation of the Moore-MacNeish Construction of MOLS for SOMAs, and more generally for a certain class of partial linear spaces. Using the Moore-MacNeish Construction of MOLS, we obtain the following known result called the Moore-MacNeish Theorem:

N(nt) ≥ min{N(n), N(t)}.

Before we give an analogue for the function M(n), we first require the following preliminaries.

Definition: The chromatic number of a graph is the smallest number of colours required to colour the vertices of the graph so that no two adjacent vertices have the same colour.

Let A be a SOMA with symbol-set Ω. We define Γ_A^c to be the graph with vertex-set Ω, where two symbols are adjacent if, and only if, these symbols are distinct and are contained in an entry of the SOMA A. We remark that this graph and the corresponding graph defined in Section 1.6 (page 40) of my PhD thesis have different names because of the difficulty in reproducing certain symbols in the HTML language. We now state an analogue of the Moore-MacNeish Theorem for M(n):

Let A be a non-Trojan SOMA(k,n) with symbol-set Ω. Suppose that N(t) is greater than or equal to the chromatic number of the graph Γ_A^c. Then M(nt) ≥ k.

This page is maintained by John Arhin.

Last updated: September 5th 2007.