Back to search

University of Leeds

Definable Sets in Finite Structures

Abstract

dc:description.abstract

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.

Degree

thesis:*
Name dc:type.qualificationname
Ph.D
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Leeds
Year dc:date.issued
2022

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ainslie, Rory Sebastian Morton
Advisors dc:contributor.advisor
  • MacPherson, Dugald
  • Mantova, Vincenzo
ORCID person:identifier.orcid

Rights

Language dc:language.dcterms_iso639_2
eng

Identifiers

dc:identifier.*
Identifier
uk.bl.ethos.874958

Chain of custody

source
Harvested from
White Rose University Consortium
Base URL
etheses.whiterose.ac.uk/cgi/oai2
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Ainslie, Rory Sebastian Morton. Definable Sets in Finite Structures. doctoral thesis, University of Leeds, 2022.