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.