The Open UniversitySkip to content

Simple extensions of combinatorial structures

Brignall, Robert; Ruškuc, Nik and Vatter, Vincent (2011). Simple extensions of combinatorial structures. Mathematika, 57(02) pp. 193–214.


This is the latest version of this eprint.

Full text available as:
PDF (Accepted Manuscript) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (208Kb)
DOI (Digital Object Identifier) Link:
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
ISSN: 2041-7942
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
Item ID: 29672
Depositing User: Robert Brignall
Date Deposited: 06 Oct 2011 08:38
Last Modified: 28 Jan 2016 21:54
Share this page:

Available Versions of this Item


Scopus Citations

Actions (login may be required)

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340