Search

This PhD thesis is formed of work completed while studying at Royal Holloway, University of London. The three chapters that form the majority of the thesis each represent distinct projects that were studied in this time. Chronologically, the research forming the first chapter, on factors in random graphs was the first to be completed, in collaboration with my supervisor, Stefanie Gerke. This culminated in the paper 'Non-vertex balanced factors in random graphs', published by the Journal of Graph Theory in 2014 [30]. The second chapter, titled Complexity on Eulerian circuits, was work done in collaboration with Iain Moffatt of Royal Holloway and Joanna A. Ellis-Monaghan and Greta Pangborn of Saint Michael's College, Colchester in the US. This work is largely encapsulated by the paper 'DNA origami and the complexity of Eulerian circuits with turning costs' published by the journal Natural Computing in 2014 [17]. The third chapter, on Adversarial resilience of matchings was work carried out in collaboration with Stefanie Gerke and Paul Balister of the University of Memphis. We aim to publish the results of this chapter in the near future.

The simple relational structures form the units, or atoms, upon which all other relational structures are constructed by means of the substitution decomposition. This decomposition appears to have first been introduced in 1953 in a talk by Fraïssé, though it did not appear in an article until a paper by Gallai in 1967. It has subsequently been frequently rediscovered from a wide variety of perspectives, ranging from game theory to combinatorial optimization. Of all the relational structures - a set which also includes graphs, tournaments and posets - permutations are receiving ever increasing amounts of attention. A simple permutation is one that maps every nontrivial contiguous set of indices to a set of indices that is never contiguous. Simple permutations and intervals of permutations are important in biomathematics, while permutation classes - downsets under the pattern containment order - arise naturally in settings ranging from sorting to algebraic geometry. We begin by studying simple permutations themselves, though always aim to establish this theory within the broader context of relational structures. We first develop the technology of "pin sequences", and prove that every sufficiently long simple permutation must contain either a long horizontal or parallel alternation, or a long pin sequence. This gives rise to a simpler unavoidable substructures result, namely that every sufficiently long simple permutation contains a long alternation or oscillation. ErdÅ s, Fried, Hajnal and Milner showed in 1972 that every tournament could be extended to a simple tournament by adding at most two additional points. We prove analogous results for permutations, graphs, and posets, noting that in these three cases we may need to extend a structure by adding (n+1)/2 points in the case of permutations and posets, and logâ (n+1) points in the graph case. The importance of simple permutations in permutation classes has been well established in recent years. We extend this knowledge in a variety of ways, first by showing that, in a permutation class containing only finitely many simple permutations, every subset defined by properties belonging to a finite "query-complete set" is enumerated by an algebraic generating function. Such properties include being an even or alternating permutation, or avoiding generalised (blocked or barred) permutations. We further indicate that membership of a permutation class containing only finitely many simple permutations can be computed in linear time. Using the decomposition of simple permutations, we establish, by representing pin sequences as a language over an eight-letter alphabet, that it is decidable if a permutation class given by a finite basis contains only finitely many simple permutations. We also discuss possible approaches to the same question for other relational structures, in particular the difficulties that arise for graphs. The pin sequence technology provides a further result relating to the wreath product of two permutation classes, namely that C â D is finitely based whenever D does not admit arbitrarily long pin sequences. As a partial converse, we also exhibit a number of explicit examples of wreath products that are not finitely based.