Projects per year
Abstract
An interval in a combinatorial structure R is a set I of points which are related to every point in R \ 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 the best possible.
Original language  English 

Pages (fromto)  193214 
Journal  Mathematika 
Volume  57 
Issue number  2 
Early online date  21 Dec 2010 
DOIs  
Publication status  Published  Jul 2011 
Fingerprint
Dive into the research topics of 'Simple extensions of combinatorial structures'. Together they form a unique fingerprint.Projects
 1 Finished

EPSRC GR/S53503/01: Applications of Automata and Languages in the Theory of Pattern Classes of Permutations
Ruskuc, N. (PI), Linton, S. A. (CoI) & Robertson, E. F. (CoI)
1/02/04 → 31/01/07
Project: Standard