Brignall, Robert; Ruškuc, Nik and Vatter, Vincent
This is the latest version of this eprint.
PDF (Accepted Manuscript)
- Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
|DOI (Digital Object Identifier) Link:||http://doi.org/10.1112/S0025579310001518|
|Google Scholar:||Look up in Google Scholar|
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 best possible.
|Item Type:||Journal Article|
|Copyright Holders:||2010 University College London|
|Keywords:||indecomposable graph; modular decomposition; prime graph; simple permutation; simple poset; simple tournament; substitution decomposition|
|Academic Unit/Department:||Mathematics, Computing and Technology > Mathematics and Statistics
Mathematics, Computing and Technology
|Depositing User:||Robert Brignall|
|Date Deposited:||06 Oct 2011 08:38|
|Last Modified:||24 Feb 2016 09:23|
|Share this page:|
Available Versions of this Item
Simple extensions of combinatorial structures. (deposited 12 Sep 2011 09:54)
- Simple extensions of combinatorial structures. (deposited 06 Oct 2011 08:38) [Currently Displayed]
Download history for this item
These details should be considered as only a guide to the number of downloads performed manually. Algorithmic methods have been applied in an attempt to remove automated downloads from the displayed statistics but no guarantee can be made as to the accuracy of the figures.