Well quasi-order and atomicity for combinatorial structures

Abstract

This thesis investigates the well quasi-order (wqo) and atomicity problems for partially ordered sets of combinatorial structures. The main contribution is to present a framework for considering these problems for combinatorial structures under consecutive orders, expanding on the methods of McDevitt and Ruskuc.

We begin by introducing the area and giving basic definitions in Chapters 1 and 2 respectively, and by presenting the required preliminary information on consecutive orders in Chapter 3.

In Chapter 4, we introduce a framework enabling us to approach the wqo and atomicity problems for a wide class of valid structures by encoding structures as paths in certain digraphs. Following this, we define two subclasses of valid structures – sparse and bountiful structures – and answer the wqo and atomicity problems for each of these.

Chapters 5 and 6 are concerned with invalid structures, for which the approach of Chapter 4 does not apply. We consider three case studies: letter overlap free words, double ascents, and forests. The wqo and atomicity problems for letter overlap free words and double ascents are answered in Chapter 5 by relating them to the analogous questions for words, which are valid. These methods are not sufficient for forests, so we extend the methods of Chapter 4 to answer the wqo problem for forests in Chapter 6.

Between sparse and bountiful structures, there is another subclass of valid structures called intermediate structures. Chapters 7 and 8 are concerned with two examples of intermediate structures: equivalence relations and equiperms respectively; we
answer the wqo and atomicity problems for each of these.

Chapter 9 considers equivalence relations under the non-consecutive order. We prove that equivalence relations are well quasi-ordered under the non-consecutive order, and that the atomicity problem is decidable.

Finally, Chapter 10 summarises and contextualises our results, and outlines directions for future research.

Date of Award	2 Jul 2026
Original language	English
Awarding Institution	University of St Andrews
Supervisor	Nik Ruskuc (Supervisor)