Definable Sets in Finite Structures

This Thesis is primarily motivated by a conjecture of Anscombe, Macpherson, Steinhorn
and Wolf [2]. The conjecture states that, for a homogeneous structure M over a finite
relational language, M is elementarily equivalent to the ultraproduct of a ‘multidimensional
exact class’ if and only if M is stable. The right to left statement has already been verified,
and so our focus is on the left to right. In this thesis, we confirm the conjecture for certain
unstable homogeneous structures such as the universal metrically homogeneous graph of
diameter k, the universal homogeneous two-graph and various others, such as the 28 ‘semi-
free’ edge-coloured homogeneous graphs described by Cherlin in the appendix of [16]. We
also provide some mechanisms for answering the question for other unstable structures.
The core of this thesis is about finite ‘n-regular’ 3-edge-coloured graphs. For any given n, a
classification of sufficiently large n-regular 3-edge-coloured graphs is expected to yield
a proof of the ‘m.e.c’ conjecture in the case of the universal homogeneous 3-coloured
graph, and indeed, our results yield some further special cases of the ‘m.e.c’ conjecture.
The main focus is on finite ‘3-regular’ 3-coloured graphs. We classify such structures
under certain conditions: when they possess a ‘complete neighbourhood’, when they are
‘monochromatic-triangle-free’ and if we increase to ‘4-regularity’ we can classify the
imprimitive case as well. In the other scenarios, we employ methods from the theory of
association schemes, together with linear algebra, to give a description of the eigenvalues
and/or eigenvectors of the neighbourhoods with respect to a base point. We also describe
the two known primitive examples of such graphs and prove they are actually homogeneous,
which implies n-regularity for each n.