Simple extensions of combinatorial structures
Mathematika, 57 (2011), 193–214.
With Robert Brignall and Nik Ruškuc.
An interval in a combinatorial structure S is a set I of points which relate to every point from S∖I in the same way. A structure is simple if it has no proper intervals. Every combinatorial structure can be expressed as an inflation of a simple structure by structures of smaller sizes — this is called the substitution (or modular) decomposition. In this paper we prove several results of the following type: An arbitrary structure S of size n belonging to a class C can be embedded into a simple structure from C by adding at most f(n) elements. We prove such results when C is the class of all tournaments, graphs, permutations, posets, digraphs, oriented graphs and general relational structures containing a relation of arity greater than 2. The function f(n) in these cases is 2, ⌈log2(n+1)⌉, ⌈(n+1)/2⌉, ⌈(n+1)/2⌉, ⌈log4(n+1)⌉, ⌈log3(n+1)⌉ and 1, respectively. In each case these bounds are best possible.